2 条题解
-
0
本题使用贪心即可,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
- 上传者