给定n个选手，将他们分成若干只队伍。其中第i个选手要求自己所属的队伍的人数大等于a[i]人。 在满足所有选手的要求的前提下，最大化队伍的总数。 注：每个选手属于且仅属于一支队伍。
第一行一个整数n，表示人数。 以下n行，每行一个整数表示a[i]。
输出队伍总数的最大值。数据保证有解。
5 2 1 2 2 3
2
对于20%的数据，n <= 10 对于40%的数据，n <= 1000 对于60%的数据，n <= 10000 对于100%的数据，1 <= n <= 10^6
最开始一看，诶，这不就是个贪心嘛，结果就只拿了50分。不过机房里的大佬，有的贪心贪了80分，还有一个贪到100分的，也不知道是怎么贪出来的。。。拿100分大佬的贪心和我后面写的DP去拍，拍到了4万多还是没有错误。（太巨了！！） 但这题贪心显然是不可行的。 最开始的贪心代码如下，
int main() { n = read(); memset(a,0,sizeof(a)); for(int i = 1; i <= n; i ++) a[i] = read(); sort(a,a + n); for(int i = n; i >= 1; i --) { if(i >= a[i]) { sum ++; i = i - a[i] + 1; } } printf("%d\n",sum); return 0; }就是从后往前，把麻烦的堆在一起，本来样例都过了，结果后面发现一个错误数据。。。
9 1 2 2 4 5 5 5 5 5
3
三组分别为（1）（2,2）（4,5,5,5,5,5）
2
从后往前分的贪心，并不能聪明到把4归进后一组，而是会让4自己新开一组，于是分组结果如下：（1,2,2,4）（5,5,5,5,5）
既然贪心是不行的，那就让我们来试试DP。后面写DP的时候也是充满坎坷啊。。。 知道了是DP之后，其实转移方程还算是蛮好找的。
for(int i = 1; i <= n; i ++) { if(i - a[i] >= 0) f[i] = max(f[i - 1],f[i - a[i]]+ 1); }然后，最烦的就是要加一个特判，如果最麻烦的那个人要求特高的话，那就整个只能全在一组里了。特判代码如下，
if(n - a[n] == 0) { f[n] = 1; }最后，附赠实验巨佬ZWT的超级注释版代码
#include <bits/stdc++.h> using namespace std; const int maxn = 1000015; //blt:最开始我maxn少写了个0，结果交到某谷上只有60分。。。 int n, a[maxn], f[maxn], g[maxn]; inline int read()//快读优化 { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { n = read(); for(int i = 1; i <= n; ++i) a[i] = read(); sort(a + 1, a + n + 1); for(int i = 1; i <= n; ++i) { f[i] = g[i - a[i]] + 1; //预留出后边儿a[i]个，后边儿最多成一组 //前面的 i - a[i]个数的最大分队数+1 g[i] = max(g[i - 1], f[i]); //预处理前面的（类似最大前缀和）分队数，求出转移最大值 } printf("%d", f[n]); //不知为啥输出f？？ //blt:这个为什么我也不清楚 //blt:或者像我的最终版DP那样加个特判也是能A的 return 0; } /* //也可直接： f[i] = max ( f[ i - 1], f[i - a[ i] ] + 1) f[ i - 1]第i个人不开新队，最大分队数不变 f[i - a[ i] ] + 1第i个人开新队，最少保证后边儿还有a[i]个人 sum = max(sum, f[i]) ↑错的！！！ //错误数据： 4 1 2 2 4 //blt:其实只是最终要记得加个特判。。。 改为： g[n] = f[i - a[ i] ] + 1 f[i] = max ( f[ i - 1], g[i]) 输出f[i] ↑还是错的！！ //blt:其实这俩是 一个效果，又没有加特判，当然错了啊 f[n]相当于标程中的g（预处理效果？？），最后应输出g[n]！！ //blt:我好像有些不明白。。。(坐看大佬zwt一本正经的胡乱bb) 再改：（对于加了一位反而所有加在一起都只能分一组的特判（？） //blt:是这样的呢 (循环内) if(i - a[i] >= 0) { g[n] = f[i - a[ i] ] + 1 f[i] = max ( f[ i - 1], g[i]) } (循环外) if(n - a[n] == 0) f[n] = 1; 输出f[n] //blt:所以最后当然是A啦，啦啦啦~ */对于一个数字对(a, b)，我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。 给定一正整数n，问最少需要多少次操作可将数字对(1, 1)变为一个数字对，该数字对至少有一个数字为n。
第一行一个正整数 n
一个整数表示答案。
5
3
(1,1) → (1,2) → (3,2) → (5,2)
对于30%的数据， 1 <= n <= 1000 对于60%的数据， 1 <= n <= 20000 对于100%的数据，1 <= n <= 10^6
这题超简单的，其实就是一个辗转相除法的变形。具体解释请详见代码，
#include<bits/stdc++.h> using namespace std; #define INF 1<<30 int read() { char ch = getchar(); int ret = 0, flag = 1; while(ch < '0'|| ch > '9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ret = ret * 10 + ch - '0'; ch = getchar(); } return ret * flag; } int magic(int a, int b) { if(!b)//要是b等于零，b显然不可能为零嘛 //最小都是(1,1)，之后又一直加的，怎么会有零 //要是说是后面取模取到整除的话，那也是不可能的，手动模拟一下就知道了 //e.g.:最简单，(2,2)，一看就知道，根本是行不通的嘛 return INF; if(b == 1)//要是b等于1，那就一直加另一边,因为另一边本来为1，所以操作数要减1 return a - 1; return magic(b, a % b) + a / b; //这个其实挺好理解的，就是 n * b + a % b = a //e.g.:(8,3) = (3,2) + 2 //也就是说，把 3 往 2 那里加两次，就可以得到(8,3)了 } int n; int now = INF; int main() { n = read(); for(int i = 1; i <= (n + 1) / 2; i ++) //只用到一半就好啦，因为前一半和后一半的结果是可以由同一个状态转移过去的 { now = min(now, magic(n,i)); //然后枚举，看看最后一步要从哪转移才能让之前的步数最小，并记录最小步数 } printf("%d\n",now); return 0; }早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。 请为这种高级打字机设计一个程序，支持如下3种操作： T x：在文章末尾打下一个小写字母x。(type操作) U x：撤销最后的x次修改操作。（Undo操作）（注意Query操作并不算修改操作） Q x：询问当前文章中第x个字母并输出。（Query操作）文章一开始可以视为空串。
第1行：一个整数n，表示操作数量。 以下n行，每行一个命令。保证输入的命令合法。
每行输出一个字母，表示Query操作的答案。
7 T a T b T c Q 2 U 2 T c Q 2
b c
对于40%的数据 n<=200; 对于100%的数据 n<=100000；保证Undo操作不会撤销Undo操作。
对于200%的数据 n<=100000；Undo操作可以撤销Undo操作。
必须使用在线算法完成该题。
大佬说：这不就是一个简单的主席树板子嘛。然而本蒟蒻并没有学过主席树。。。
