社区讨论
民间数据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 条回复,欢迎继续交流。
正在加载回复...