P14635 [NOIP2025] 糖果店 / candy（民间数据）题解

· · 题解

P14635 [NOIP2025] 糖果店 / candy（民间数据）题解

首先, 每种糖果的选取分为两部分：

  1. A 部分：单独的一个 x_i
  2. B 部分：多组 x_i+y_i

只会有一种糖果会有 B 部分，即 x_i+y_i 最小的那种。因为如果有其他糖果包含 B 部分，可以用这种糖果进行替代。

A 部分是独立的，贪心地尽量取 x_i 小的即可。最后，我们枚举 k，取 x_i 前 k 小的 x_i，剩下的则全是 B 部分。

#include<cstdio>
#include<algorithm>
using namespace std;

#define N 100005
#define int long long

namespace code
{
    int n,m;
    struct candy
    {
        int x,y;
    } candies[N];

    signed main()
    {
        scanf("%lld%lld",&n,&m);
        int t=9e18;
        for(int i=1;i<=n;++i)
            scanf("%lld%lld",&candies[i].x,&candies[i].y),
            t=min(t,candies[i].x+candies[i].y);
        sort(candies+1,candies+n+1,[](candy a,candy b){return a.x<b.x;});
        int ans=m/t<<1;
        for(int i=1;i<=n;++i)
            if((m-=candies[i].x)>=0)
                ans=max(ans,i+(m/t<<1));
        printf("%lld",ans);
        return 0;
    }
}

signed main()
{
    code::main();
    return 0;
}