专栏文章

题解：P????? [NOIP2025] 纯糖 Kards（kandy）

ssLMxf
P14635题解参与者 19已保存评论 20

文章操作

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

当前评论
9 条
当前快照
1 份
快照标识符
@mimyw5ye
此快照首次捕获于
2025/12/01 17:49
3 个月前
此快照最后确认于
2025/12/01 17:49
3 个月前
查看原文
考场只切了这道题，好菜啊。
好像忘记判断能否拿完前面一段糖了，预计 100->0。
历程：
  • 8:30 看题。
  • 8:35 写完代码。
  • 8:38 过了所有大样例。
  • 综上所述，废物
本文为交互式。

题意

你在玩 Kards，你获得了一张 00 费精英指令牌“糖果”。你还有 nn 个单位。一开始，每个单位的花费仅为 1018+110^{18}+1。
  • “糖果”：使用后，对于第 ii 个单位，第奇数次部署时，此单位花费为 xix_i；第偶数次部署时，此单位花费为 yiy_i。
现在，你有 mm 指挥点。作为一名 25 段的新兵，你决定放置尽量多的单位。问可以放置多少个。
n≤105,m≤1018n\le 10^5,m\le 10^{18}。

解法

Tip 1
如果只部署一个单位，且只部署偶数次，如何最优？
Answer 1
注意到部署一个单位 2k2k 次，花费为 k(xi+yi)k(x_i+y_i)。
所以部署 xi+yix_i+y_i 最少的。
以下记 sum=xi+yisum=x_i+y_i。
Tip 2
如果添加了其他的 pp 个单位，花费为 kk，现在你只部署一个单位偶数次，答案是多少？
Answer 2
你还剩下 m−km-k 的指挥点，这些指挥点可以部署 2×⌊m−ksum⌋2\times \left\lfloor\dfrac{m-k}{sum}\right\rfloor 次。
Tip 3
能否证明，其他单位（除开 xi+yix_i+y_i 的那一个）最多选一次？
Answer 3
假设我们还选择了 jj，部署了 22 次。
可以发现，xj+yj≥sumx_j+y_j\ge sum。
那你将这两次部署换成 sumsum 显然不亏。
更多次同理。
得证。
Tip 4
如何求解答案。
Answer 4
由于其它单位最多选一次，考虑枚举这个值。
这个可以证明：选 xix_i 最小的几个是最优秀的。
对 xix_i 排序即可。

代码

codeCPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int x[N],y[N];
signed main()
{
	int n,m,sum=LLONG_MAX,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i],sum=min(sum,x[i]+y[i]);
	sort(x+1,x+n+1);
	for(int i=0;i<=n;i++)
	{
		m-=x[i];
		if(m<0) break;
		ans=max(ans,i+m/sum*2);
	}
	cout<<ans<<'\n';
	return 0;
}

评论

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

正在加载评论...