SG Value
Problem's Link: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1554
Mean:
一个可重集合，初始为空，每次插入一个值，询问这个集合的SG值(集合中的数字组合相加不能达到的最小值)是多少。
analyse:
这题方法很巧妙。
假设当前不能达到的最小值为v，对于要插入的一个新值x
1)如果x>v,那么v的值不会改变，我们用一个优先队列(从小到大)将x进队;
2)如果x<=v，那么v的值会改变为v+x，然后再判断队列中的元素，把队列中的元素当作新值x来处理，执行1、2操作,这样就能保证v一直是不能达到的最小值。
Time complexity: O(n)
Source code:
// Memory Time // 1347K 0MS // by : crazyacking // 2015-03-29-18.44 #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<climits> #include<iostream> #include<algorithm> #define MAXN 1000010 #define LL long long using namespace std; priority_queue<LL,vector<LL>,greater<LL> > q; int main() { ios_base::sync_with_stdio(false); cin.tie(0); // freopen("C:\\Users\\Devin\\Desktop\\cin.cpp","r",stdin); // freopen("C:\\Users\\Devin\\Desktop\\cout.cpp","w",stdout); LL t; while(cin>>t) { LL v=0;// biggest num while(!q.empty()) q.pop(); while(t--) { LL type; cin>>type; if(type==1) // insert { LL num; cin>>num; if(num>v+1) { q.push(num); } else { v+=num; while(!q.empty()) { LL tmp=q.top(); if(tmp<=v+1) { v+=tmp; q.pop(); } else break; } } } else cout<<v+1<<endl; } } return 0; } /* */ /************************************************************** Problem: 1554 User: crazyacking Language: C++ Result: Accepted Time:396 ms Memory:1996 kb ****************************************************************/
