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 #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #define MAXN 1000010 #define LL long long using namespace std; priority_queue
                  
                   
                    ,greater
                    
                      > 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<
                     
                      <

View Code

转载于:https://www.cnblogs.com/crazyacking/p/4376694.html

你可能感兴趣的文章