Problem - C - Codeforces
题意:
思路:
在check的时候,我们要尽量用算贡献的思想,并且大胆贪心
文章来源:https://www.toymoban.com/news/detail-614627.html
Code:文章来源地址https://www.toymoban.com/news/detail-614627.html
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mxn=3e5+10;
const int mxe=3e5+10;
const int mod=1e9+7;
int N;
int a[mxn];
bool check(int day,int val){
int cnt1=(day+1)/2;
int cnt2=day/2;
for(int i=1;i<=N;i++){
int ned2=min((val-a[i])/2,cnt2);
int ned1=val-a[i]-ned2*2;
cnt2-=ned2;
cnt1-=ned1;
}
return cnt1>=0&&cnt2>=0;
}
void solve(){
cin>>N;
for(int i=1;i<=N;i++) cin>>a[i];
sort(a+1,a+1+N);
int mx=a[N];
int l=0,r=1e18;
int ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(mid,mx)||check(mid,mx+1)){
ans=mid;
r=mid-1;
}else l=mid+1;
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int __=1;cin>>__;
while(__--)solve();return 0;
}
到了这里,关于【二分答案】CF1661 C的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!