社区讨论

民间数据100pts,但样例6输出小1求反例

P14635[NOIP2025] 糖果店参与者 4已保存回复 6

讨论操作

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

当前回复
6 条
当前快照
1 份
快照标识符
@mikidaqm
此快照首次捕获于
2025/11/30 00:31
3 个月前
此快照最后确认于
2025/12/01 21:50
3 个月前
查看原帖
复现的考场做法,应该是复现一致了。
https://www.luogu.com.cn/record/250545274
CPP
#include <bits/stdc++.h>

using namespace std;
const int maxn = 100004;
int n;
long long m;

int main()
{
	// freopen("candy7.in", "r", stdin);
	// 这个代码和场上代码一样地在第六个点输出 82 instead of 83 
	cin.tie(0); ios::sync_with_stdio(0);
	cin>>n>>m;
	priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> >> pq;
	for(int i=1;i<=n;i++)
	{
		long long x, y;
		cin>>x>>y;
		pq.push({x*2, y*2});
		pq.push({x+y, -1});
	}
	long long ans = 0;
	while(!pq.empty())
	{
		auto u = pq.top();
		if(u.second == -1)
		{
			if(m - u.first < 0)
			{
				pq.pop();
				continue;
			}
			long long cost = m/u.first;
			m -= u.first*cost;
			ans += cost * 2;
			continue;
		}
		if(m - u.first/2 < 0) break;
		m -= u.first/2;
		ans++;
		pair<long long, long long> cur = {u.second, u.first};
		pq.pop();
		pq.push(cur);
	}
	cout<<ans<<'\n';
	return 0;
}

思路是取性价比最高的,放到优先队列维护(小根堆),这里合并的部分的权设置了二分之一,然后做法是两种情况权值都乘以二来表示整数。

回复

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

正在加载回复...