P14635 [NOIP2025] 糖果店

zhlzt · 2025-11-29 14:14:02 · 题解

分拆成 x+y 和单独的 x 考虑。

对于 x 从小到大排序，枚举，选最小的 i 个。

对于 x+y，使用剩余的钱重复选取最小的 x+y。

时间复杂度 \mathcal{O}(n\log n)，瓶颈在于排序。

记得判 m<\text{sum}(\text{prefix}(i))，我场上没判。/ll

:::success[[NOIP2025] 糖果店 - candy.cpp]

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int valx[maxn],valy[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;cin>>n;
    long long m;cin>>m;
    int val=2e9;
    for(int i=1;i<=n;i++){
        cin>>valx[i]>>valy[i];
        val=min(val,valx[i]+valy[i]);
    }
    sort(valx+1,valx+1+n);
    long long ans=(m/val)*2,sum=0;
    for(int i=1;i<=n;i++){
        sum+=valx[i];
        if(m>=sum) ans=max(ans,((m-sum)/val)*2+i);
    }
    cout<<ans<<"\n";
    return 0;
}

:::