给出一个非减序的数组a[n], 然后得到s=2^a1+.……+2^an， 要使s为2^v -1,需要在数组中添加几个数。
我的思路是这样的，由2^a+2^a = 2^(a+1)可知，如果有两个连续的数a，我们可以把他们合并为a+1放入集合中，使集合中没有重复的数，我可以用stl里的set。如果想要满足题目中的要求，集合中必须有最大那个数个元素，缺多少就可以计算出来了。
代码：
//codeforces 305 C. Ivan and Powers of Two //2013-06-05-17.19 #include <stdio.h> #include <set> #include <algorithm> #include <iostream> using namespace std; set<int> s; int main() { int n, a; while (scanf("%d", &n) != EOF) { s.clear(); int maxn = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a); while (s.count(a)) { s.erase(a); a++; } s.insert(a); maxn = max(a, maxn); } printf("%d\n", maxn-s.size()+1); } return 0; }
