math --- CSU 1554: SG Value

时间:2021-08-20 11:33:33

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();
// 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=;// biggest num
while(!q.empty()) q.pop();
while(t--)
{
LL type;
cin>>type;
if(type==) // insert
{
LL num;
cin>>num;
if(num>v+)
{
q.push(num);
}
else
{
v+=num;
while(!q.empty())
{
LL tmp=q.top();
if(tmp<=v+)
{
v+=tmp;
q.pop();
}
else break;
}
}
}
else cout<<v+<<endl;
}
}
return ;
}
/* */ /**************************************************************
Problem: 1554
User: crazyacking
Language: C++
Result: Accepted
Time:396 ms
Memory:1996 kb
****************************************************************/