[NOIP2025] 糖果店 / candy

_H17_ · 2025-11-29 13:59:48 · 题解

前言

NOIP 最成功的部分，补上代码了。

题目分析

考虑如果一个东西选好几次那这个东西的 x+y 一定最小，不然替换成最小的一定更优。

其他肯定选 x 最小的，枚举选到哪一个，剩下用最小的 x+y 补齐即可。

时间复杂度 O(n\log n)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=1e5+1;
int n,m,gsum,ans;
pair<int,int>a[N];
signed main(){/*
    freopen("candy.in","r",stdin),
    freopen("candy.out","w",stdout);*/
    ios::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1,x,y;i<=n;i++){
        cin>>x>>y;
        a[i]={x,y};
    }
    sort(a+1,a+n+1,[](pair<int,int>a,pair<int,int>b)->bool{
        if(a.first+a.second!=b.first+b.second)
            return a.first+a.second<b.first+b.second;
        else
            return a.first<b.first;
    });
    gsum=(a[1].first+a[1].second);
    sort(a+1,a+n+1,[](pair<int,int>a,pair<int,int>b)->bool{
        return a.first<b.first;
    });
    ans=(m/gsum)*2;
    for(int i=1,sum=0,cnt=0;i<=n;i++){
        sum+=a[i].first,cnt++;
        if(sum>m)
            break;
        ans=max(ans,cnt+((m-sum)/gsum)*2);
    }
    cout<<ans;
    return 0;
}