P14635 [NOIP2025] 糖果店

分拆成

x+y

和单独的

x

考虑。

对于

x

从小到大排序，枚举，选最小的

i

个。

对于

x+y

，使用剩余的钱重复选取最小的

x+y

。

时间复杂度

\mathcal{O}(n\log n)

，瓶颈在于排序。

记得判

m<\text{sum}(\text{prefix}(i))

，我场上没判。/ll

[NOIP2025] 糖果店 - candy.cpp

CPP

1234567891011121314151617181920212223#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;
}

P14635 [NOIP2025] 糖果店

文章操作

相关推荐

评论

P14635 [NOIP2025] 糖果店