Codeforces Round 961 (Div. 2) B2. Bouquet (Hard Version)

本文主要是介绍Codeforces Round 961 (Div. 2) B2. Bouquet (Hard Version)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

写在前面
思路
code

B2. Bouquet (Hard Version)

写在前面

今天下午写这道题时，有思路却没写出来，后面看了一下别人写的代码豁然开朗，这道题其实挺简单的，没写出来只能说 ~~我太菜了QAQ~~

思路

考点：排序+贪心

首先我们可以在序列中任意组合
那么这个序列的初始排序并不重要，我们可以先将序列进行升序排序

排完序后，对于这题而言，无非就两种情况：

后一个数减当前的数大于1，那么只能选当前的数
后一个数减当前的数等于1，那么2个数都要考虑

第一种情况没什么好说的，重点在于第二种情况：

如果两个数全部选完，并且不大于m，那就让这个值与ans比较大小即可

反之，我们可以运用贪心的策略，我们先全部选小的数，如果还有剩余硬币，在选大的数
由于大的数跟小的数差值为1，我们可以将小的数替换成大的数，让它的硬币数+1

思路不难，接下来看代码~~

code

PII a[N];
void solve(){int n,m;cin >> n >> m;for(int i=1;i<=n;++i) cin >> a[i].fi;for(int i=1;i<=n;++i) cin >> a[i].se;sort(a+1,a+1+n);int ans=0;a[n+1].fi=0,a[n+1].se=0;//相当于初始化for(int i=1;i<=n;++i){if(a[i+1].fi-a[i].fi==1){int temp=a[i].fi*a[i].se+a[i+1].fi*a[i+1].se;//全部选if(temp<=m) ans=max(ans,temp);else{int k=min(a[i].se,m/a[i].fi);//先选小的temp=k*a[i].fi;int t=min(a[i+1].se,(m-temp)/a[i+1].fi);temp+=t*a[i+1].fi;//还有剩余，再选大的if(k && t<a[i+1].se && temp<m){//判断是否可以进行替换int s=min(min(k,a[i+1].se-t),(m-temp));temp+=s;}ans=max(ans,temp);}}else{int k=min(a[i].se,m/a[i].fi);int temp=k*a[i].fi;ans=max(ans,temp);}}cout << ans << endl;return ;
}