【二分答案】CF1661 C

小咪咪 2024-03-22 20:25 41阅读 0赞

[Problem - C - Codeforces][]

题意：

![b7962e76b90c402e95ec6324c654b1fa.png][]

思路：

在check的时候，我们要尽量用算贡献的思想，并且大胆贪心

![df03bde027f84d50abfbfb212ef5f9ed.png][]

Code：

#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; 
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1661/problem/C
[b7962e76b90c402e95ec6324c654b1fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/59880f3127784c278d98c627423cc890.png
[df03bde027f84d50abfbfb212ef5f9ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/0a80bc86ad7a45e7b6892ef21b089f26.png

发表评论取消回复

表情：

评论列表（有 0 条评论，41人围观）

还没有评论，来说两句吧...

相关阅读

相关 C. Computer Game——（普通二分查找）（CF-1400）

题目： [题目连接][Link 1] 该题的题意是： Vova在打电脑游戏，他很想打完这局游戏 ①起初，他的电脑有**k**的电量，这局游戏有**n**...

矫情吗；*/ 2024年04月18日 13:01/ 0 赞/ 39 阅读

相关二分答案总结

二分的三种实现形式： 1.最普通的： while(l<=r){ int mid=l+r>>1; if(check(m

曾经终败给现在/ 2024年03月30日 09:30/ 0 赞/ 55 阅读

相关【贪心+二分】CF1791G2

[Problem - 1791G2 - Codeforces][] 题意： ![1207a1f598e74fa39c4b7b9aff9f9e40.png][] ![19d

柔光的暖阳◎/ 2024年03月23日 23:39/ 0 赞/ 71 阅读

相关【二分答案】CF803 D

感觉之前的\1900好简单 [Problem - D - Codeforces][] 题意： ![47e9ce79fee54c63a55acba3cac6e937.pn

客官°小女子只卖身不卖艺/ 2024年03月23日 22:41/ 0 赞/ 48 阅读

相关【二分+贪心】CF1622 C

[Problem - 1622C - Codeforces][] 题意： ![f6cd9c72cb09404e95da429847de7fb5.png][] ![fdc7

古城微笑少年丶/ 2024年03月23日 21:59/ 0 赞/ 72 阅读

相关【二分+贪心】CF1665 C

[Problem - C - Codeforces][] 题意： ![acbe9c1d054143bb8090042f525333b9.png][] ![557b7c06

比眉伴天荒/ 2024年03月23日 21:45/ 0 赞/ 28 阅读

相关【二分答案】CF1661 C

[Problem - C - Codeforces][] 题意： ![b7962e76b90c402e95ec6324c654b1fa.png][] 思路：在chec

小咪咪/ 2024年03月22日 20:25/ 0 赞/ 42 阅读

相关【二分or双指针】CF856div2 C. Scoring Subsequences

感觉对CF的套路题稍微有点感觉了考虑特殊条件性质就好了.... [Problem - C - Codeforces][] 题意：定义一个序列的分数为s1\s2\s3

布满荆棘的人生/ 2024年03月22日 10:36/ 0 赞/ 58 阅读

相关数学二分——cf700A

二分答案 include<bits/stdc++.h> using namespace std; define ll long long i

╰半橙微兮°/ 2023年10月12日 08:20/ 0 赞/ 11 阅读

相关二分答案学习笔记

内容先![1660941-20190626085335054-1727597896.png][] 等我多做些题在来写转载于:https://www.cnblogs.c

谁践踏了优雅/ 2021年11月02日 09:16/ 0 赞/ 337 阅读