社区讨论

数据太水了,真建议大修此题

P3045[USACO12FEB] Cow Coupons G参与者 5已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lo8jfmsw
此快照首次捕获于
2023/10/27 19:36
2 年前
此快照最后确认于
2023/10/27 19:36
2 年前
查看原帖
第一次尝试的时候,随手打了一份这个代码:
C
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e4+10;
ll n,m,k,ans,sum;
priority_queue<pair<int,int> >p;
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
	scanf("%lld%lld%lld",&n,&k,&m);
	for(int i=1;i<=n;i++)
	{
		ll a,b;
		scanf("%lld%lld",&a,&b);
		p.push(make_pair(-b,a));
	}
	while(k--)
	{
		ll t=-p.top().first;
		ll x=p.top().second;
		p.pop();
		if(sum+t>m)break;
		sum+=t;
		ans++;
	}
	while(p.size())
	{
		ll t=-p.top().first;
		ll x=p.top().second;
		p.pop();
		q.push(x);
	}
	while(q.size())
	{
		ll x=q.top();
		q.pop();
		if(sum+x>m)break;
		sum+=x;
		ans++;
	}
	printf("%lld\n",ans);
		
	
	return 0;
}
令人震惊的是得了80多分!
这个代码意思是把手中的k个消费券一股脑都用给最小的,第一个大根堆是pair,第一个按优惠从小到大入堆,第二个按原价从大到小。
全用完后就把大根堆剩余的给小根堆,小根堆选取价格最低的
这么水的数据加个特判不就A了
建议管理员大改一下这个题,尤其是加强数据

回复

5 条回复,欢迎继续交流。

正在加载回复...