返回题解分享
讨论 / 题解分享/ 帖子详情

村长选举 - 题解

本题使用贪心即可,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;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!