P14635 [NOIP2025] 糖果店 / candy 题解

· · 题解

前言

考场的想法，结果2.5h都还有一些细节没处理好导致有点小爆炸。

思路

首先阅读题目和样例，根据样例1可以发现：对于大量购买同一种糖果的情况，平均每颗的价格为 \frac{x_i + y_i}{2}。因此 x_i + y_i 最小的糖果在批量购买时最优，可以想到去找到这颗糖果 p 并大量购买。

再看到样例2，发现我们不能只买 p 这一个糖果，因为可能有其他的糖果在第一次购买时的价格比 p 的更便宜，买了后的糖果数比只买 p 的更多。这些糖果 i 的第一颗价格 x_i 很低，但第二颗价格 y_i 很高，平均价格不优，只适合买一颗。

可以发现对于 p 以外的糖果，买 x 较小的糖果肯定比买 x 较大的糖果优，因此我们就可以对价格按 x 从小到大排序，之后枚举买前 k 颗其他糖果的情况并统计其买的钱数 sum，然后用 m 减去 sum 得到剩余的钱数去计算买 p 的个数，取每种情况的最大值即可。

有人可能会问：假如说单买的糖果里有可以买第二颗的情况怎么办？但这其实不会成立，如果单买的糖果 i 可以买第二颗，则需要花费 x_i + y_i，但此时 x_i + y_i \ge x_p + y_p，同样的钱用来买 p 糖果必定可以得到 2 颗，甚至还有可能可以再买一颗 p，而买 i 只能得到 2 颗，总糖果数没有更优，因此不会选择买 i 的第二颗。

时间复杂度

主要集中在 sort 的排序上，为 O(nlogn)，枚举是 O(n) 的，计算钱数和颗数都是 O(1) 的，因此总复杂度是 O(nlogn)。

代码

一些解释和注意事项都写在注释里了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,mn=1e18,p;
struct node
{
    ll x,y;
}cd[100005];
bool cmp(node a,node b)
{
    if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}
ll check(ll sum,ll nk)//算买p的颗数并加到当前情况的答案中，注意这里的数据类型是long long
{
    ll w=m-sum;//剩余的钱数，注意这里的数据类型也是long long
    nk+=(w/mn)*2;
    if(w-(w/mn)*mn>=cd[p].x) nk++;//求买p的颗数，注意这里等于的时候也是可以买一颗p的
    return nk;
} 
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> cd[i].x >> cd[i].y;
        mn=min(mn,cd[i].x+cd[i].y);//mn是x+y最小值
    }
    sort(cd+1,cd+n+1,cmp);
    for(int i=1;i<=n;i++) if(cd[i].x+cd[i].y==mn) p=i;//p是x+y最小的位置 
    ll sum=0,ans=check(0,0),mk=0;//mk是当前买的散的糖果数，注意ans一开始要为只买p糖果时的答案
    for(int i=1;i<=n;i++)
    {
        if(i==p) continue;//糖果p在后面check函数中会单独统计，因此在这里不考虑
        sum+=cd[i].x;
        if(sum>m) break;//超过m就说明这颗和之后的糖果都买不下了
        mk++;
        ans=max(ans,check(sum,mk));
    }
    cout << ans;
    return 0;
}