2020牛客多校第八场 K

对于最大人数，由题可以知道第一盘有多少个，就最多有多少个人
由题可以把利润求一个前缀和。b数组其实就是控制当前前缀合最多有多少个。

将他们合并按前缀和的大小和能选的个数排序（这里前缀和小于第一个就不用加进去了，还不如选第一个）。之后我们只需要从大的开始选，能选就得把它选完，这就表明了它之后的前缀和都不能选了，而它之后的前缀有一个特点就是 b数组严格小于等于它。这样选完后结果就出来了。

要开__int128

代码：

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #include<bits/stdc++.h> #define int long long using namespace std; typedef pair<__int128,int> pii; typedef long long ll; const int INF = 0x3f3f3f3f; const double eps = 1e-5; const int mod = 998244353; const int N = 100010; int a[N],b[N]; __int128 sum[N],ans = 0; vector<pii> ve; void print(__int128 x) { if(x<0){putchar('-');x=-x;} if(x>9) print(x/10); putchar(x%10+'0'); } bool cmp(pii x,pii y){ if(x.first == y. first) return x.second > y.second; return x.first > y.first; } signed main(){ //	IOS; #ifdef ddgo freopen("C:/Users/asus/Desktop/ddgoin.txt","r",stdin); #endif int tt,z=0; cin>>tt; while(tt --){ ve.clear(); b[0] = INF; ans = 0; int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i],sum[i] = sum[i-1]+a[i]; for(int i=1;i<=n;i++) cin>>b[i],b[i] = min(b[i],b[i-1]); for(int i=1;i<=n;i++) if(sum[i] >= a[1]) ve.push_back({sum[i],b[i]}); sort(ve.begin(),ve.end(),cmp); int k = 0; for(auto i:ve){ __int128 res = i.first;int cnt = i.second; if(cnt > k){ ans += res*(cnt-k); k = cnt; } } printf("Case #%lld: %lld ",++z,b[1]); print(ans);puts(""); } return 0; } 

本文地址：https://blog.csdn.net/qq_45604735/article/details/107770113