本文共 1355 字，大约阅读时间需要 4 分钟。
题意：给你一个集合，动态插入 ，动态询问，然后问你这个集合的sg值（这个集合用加法运算不能产生的那个最小正整数）是多少.
解题思路：假设我们现在的这个SG值是 x
1）现在插入集合里面一个数v 如果这个v > x ,那么显然 sg值x不变， 把v放进从小到大的优先队列中
2）如果这个 v <= x 那么sg值x肯定就会变成 x + v, 每更新一次 sg值，就去看优先队列top元素是否是 小于等于 x的 ，如果小于等于，其实就等于把这个top元素进行1操作，这样就不会错了。
解题代码：
1 // File Name: h.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月28日 星期六 16时28分10秒 4 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 #define LL long long26 27 using namespace std;28 int t;29 priority_queue ,greater > qu;30 int main(){31 //freopen("input","r",stdin);32 //freopen("output","w",stdout);33 while(scanf("%d",&t)!= EOF)34 {35 while(!qu.empty())36 qu.pop();37 LL l,r;38 l = r = 0 ; 39 int op,v;40 for(int i = 1; i<= t ;i ++)41 {42 scanf("%d",&op);43 if(op == 1)44 { 45 scanf("%d",&v);46 if(v <= r +1)47 {48 r += v;49 while(!qu.empty())50 {51 int tmp = qu.top();52 if(tmp <= r+1)53 {54 r += tmp;55 qu.pop();56 }else{57 break;58 }59 }60 }else{61 qu.push(v);62 }63 }else{64 printf("%lld\n",r+1);65 }66 }67 }68 return 0;69 }
转载于:https://www.cnblogs.com/zyue/p/4375267.html
