2 条题解

  • 0
    @ 2025-3-29 11:01:49

    本题使用贪心即可,code开始会有n个区域内的ai的山羊支持他,而dash开始是没有羊支持的,但是他分一堆干草可以获得该区域山羊的支持,也可以获得绵羊的支持,该区域的山羊从支持code变为支持dash,所以他获得的贡献就是2*ai+bi

    #include<cstdio>
    #include<iostream>
    #include<vector>
    #include<map>
    #include<cstring>
    #include<array>
    #include<queue>
    #include<algorithm>
    #include<set>
    #include<cmath>
    using namespace std;
    using i64=long long;
    //using i128=__int128;
    const i64 INF=1e18;
    const int mod=998244353;
    //const int N=1e9+7;
    void solve(){
        int n;
        cin>>n;
        vector<int>a(n+1),b(n+1);
        i64 sum=0;
        for(int i=1;i<=n;i++)cin>>a[i]>>b[i],sum+=a[i];
        vector<i64>ans;
        for(int i=1;i<=n;i++)ans.push_back(2ll*a[i]+b[i]);
        sort(ans.begin(),ans.end(),greater<i64>());
        i64 cnt=0;
        i64 s=0;
        for(int i=0;i<n;i++){
            s+=ans[i];
            cnt++;
            if(s>sum)break;
        }
        cout<<cnt<<'\n';
    }
    int main(){
        int _=1;
        //cin>>_;
        while(_--)solve();
        return 0;
    }
    

    信息

    ID
    296
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    72
    已通过
    16
    上传者