problem-solved's blog

By problem-solved, 12 years ago, In English

CF 191B

#include<cstdio>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 lld;
multiset<int> Q;
int a[100010];
int main()
{
	int n,k,i;
	lld sum=0,b;
	scanf("%d%d",&n,&k);
	scanf("%I64d",&b);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	int ans=n;
	for(i=n-k+1;i<n;i++)
	{
		sum+=a[i];
		Q.insert(a[i]);
	}
	for(i=n-k;i>=1;i--){
		sum+=a[i];
		if(sum>b)  ans=i;
		Q.insert(a[i]);
		int tmp=*Q.begin();
		sum-=tmp;
		Q.erase(Q.begin());//it's wrong if I erase the key number like Q.erase(tmp),it may erase many numbers
	}
	printf("%d\n",ans);
	return 0;
}
Tags stl
  • Vote: I like it
  • -21
  • Vote: I do not like it