题解：P????? [NOIP2025] 纯糖 Kards（kandy）
sLMxf
·
·
题解
考场只切了这道题，好菜啊。
好像忘记判断能否拿完前面一段糖了，预计 100->0。
历程：
- 8:30 看题。
- 8:35 写完代码。
- 8:38 过了所有大样例。
- 综上所述，废物
本文为交互式。
题意
你在玩 Kards，你获得了一张 0 费精英指令牌“糖果”。你还有 n 个单位。一开始，每个单位的花费仅为 10^{18}+1。
- “糖果”：使用后，对于第 i 个单位，第奇数次部署时，此单位花费为 x_i；第偶数次部署时，此单位花费为 y_i。
现在，你有 m 指挥点。作为一名 25 段的新兵，你决定放置尽量多的单位。问可以放置多少个。
## 解法
:::info[Tip 1]
如果只部署一个单位，且只部署偶数次，如何最优？
:::
:::success[Answer 1]
注意到部署一个单位 $2k$ 次，花费为 $k(x_i+y_i)$。
所以部署 $x_i+y_i$ 最少的。
以下记 $sum=x_i+y_i$。
:::
:::info[Tip 2]
如果添加了其他的 $p$ 个单位，花费为 $k$，现在你只部署一个单位偶数次，答案是多少？
:::
:::success[Answer 2]
你还剩下 $m-k$ 的指挥点，这些指挥点可以部署 $2\times \left\lfloor\dfrac{m-k}{sum}\right\rfloor$ 次。
:::
:::info[Tip 3]
能否证明，其他单位（除开 $x_i+y_i$ 的那一个）最多选一次？
:::
:::success[Answer 3]
假设我们还选择了 $j$，部署了 $2$ 次。
可以发现，$x_j+y_j\ge sum$。
那你将这两次部署换成 $sum$ 显然不亏。
更多次同理。
得证。
:::
:::info[Tip 4]
如何求解答案。
:::
:::success[Answer 4]
由于其它单位最多选一次，考虑枚举这个值。
这个可以证明：选 $x_i$ 最小的几个是最优秀的。
对 $x_i$ 排序即可。
:::
## 代码
:::success[code]
```cpp
#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;
}
```
:::