题意： 先给你一个整数n 再给你n个数字p[i] 每个数字都在1~n之间且不重复 你 可以选择任意一个数放到最左边或者最右边 求最小的操作数使得该数组是单调递增的即 1 2 3 4 ——n 思路： 首先我们想到如果要求最小的操作 是不是在例如在 1 2 3 6 7 4 5 数组中筛去不该有的数字并且放到一边去 在我举的第一个例子中很容易看到6和7是破坏了规则的人 那不妨再看一组例子 1 2 8 3 6 7 4 5 我们又能看到 8 6 7是破坏规则的数字 而这个样例的答案是 3 也就是把8 6 7移动到后面 进一步延伸 为什么我们要把 8 6 7移出去呢？ 因为 1 2 3 4 5 是理论上最长的连序串 而8 6 7是多余的由此我们看出来了 我们需要在整个数组中找到一个最长x x+1 x+2——x+y 这样的数组 我不需要管里面是否掺进去了杂质 因为最终的杂质都被我推出去了（要么推左边 要么推右边） 代码：
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <cstdio> #include <set> #include <math.h> #include <algorithm> #include <queue> #include <iomanip> #include <stack> using namespace std; const int N=1e5+10; int n; struct sa { int num,val; }a[N]; int cmp(const sa &a,const sa &b) { return a.val<b.val; } int ans[N]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i].val); a[i].num=i; } sort(a+1,a+1+n,cmp); int val=1; ans[1]=1; for (int i=2;i<=n;i++) { if (a[i].num>a[i-1].num) { ans[i]=ans[i-1]+1; } else { ans[i]=1; } val=max(ans[i],val); } printf("%d\n",n-val); return 0; }题意： 输入一个n,m 分别是点数和边数 然后输入m个边 a[j]为第j条边的权值 b[j]若为1表示是最小生成树的边，0则不是 接下来你根据输入的边判断能否生成相应的图 若不能输出-1 若能根据每条边生成相应的两个点 思路： 显然我们能知道一个顶点为n的连通图的最大边数为(n-1)*n/2 而它的最小生成树的边数为n-1 所以我们可以想到每进去一个边就多一个顶点 它容许的空边 即非最小生成树的边为(n-1)*n/2-(n-1) 所以每次有最小生成树的边进入时顶点+1 而空边进入时则判断有没有超过最大容许数 最后生成顶点时需要注意 你的最小生成树的边根据权值大小从1-2 2-3——n-1-n排列 而空边则根据权值大小 1-3 1-4 2-4 1-5排列 代码：
