专栏文章

P14635 [NOIP2025] 糖果店 / candy 题解

ZZskioaert1106
P14635题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimyshry
此快照首次捕获于
2025/12/01 17:46
3 个月前
此快照最后确认于
2025/12/01 17:46
3 个月前
查看原文
题目传送门：P14635 [NOIP2025] 糖果店 / candy

题目分析

有一个关键的结论：只有一个 yiy_i 会被选，并且选择序列里会有这对 xi,yix_i,y_i 漫长的交替轮回。根据贪心策略，这对 xi+yix_i+y_i 是 nn 对里最小的。
证明：假如有另一个 yjy_j 被选了，则 xjx_j 肯定也被选过，同时 xi+yi⩽xj+yjx_i + y_i \leqslant x_j + y_j，将这对 xj,yjx_j,y_j 替换成 xi,yix_i,y_i 更优或不劣。
既然这样，除了这对 xi,yix_i,y_i 以外我们选的元素只有 O(n)O(n) 个。我们可以采取比较随便的做法。
记 xi+yi=Kx_i+y_i = K。
我们先假设 mm 全用来选这对了，容易得出糖果有 2⌊mK⌋2 \lfloor \dfrac{m}{K} \rfloor 颗，剩余钱数就模一下 KK。
然后对于剩下的 xjx_j 们，先升序排序，从小到大遍历，遍历到 jj 时我们计算除了 xi,yix_i,y_i 以外还恰选取了 x1∼xjx_1 \sim x_j 的结果（此处的下标是排序后的，所以选一个贵的糖之前肯定把便宜的都选过了）。
我们用反悔贪心的思想，如果当前 mm 小于 xjx_j，则把之前选的 xi,yix_i,y_i 退回去，拿着要回来的钱买新的。
最后把所有时候取 min⁡\min 即可。

代码实现

复现的考场代码，应该差不多。
CPP
#include<iostream>
#include<algorithm>
using namespace std;
constexpr int N=100005;
int n,x[N],y[N],I=1,i,K;
long long m,sum,ans,cnt;
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++){
    	cin>>x[i]>>y[i];
    	if(x[i]+y[i]<x[I]+y[I])I=i;
	}
	K=x[I]+y[I];
	ans=sum=cnt=m/K*2;
	cnt/=2,m%=K;
	sort(x+1,x+1+n);
	for(i=1;i<=n;i++){
		while(cnt>0&&m<x[i])m+=K,cnt--,sum-=2;
		if(m<x[i])break;
		m-=x[i],sum++;
		ans=max(ans,sum);
	}
	cout<<ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...