【二分答案】CF1661 C

这篇具有很好参考价值的文章主要介绍了【二分答案】CF1661 C。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem - C - Codeforces

题意:

【二分答案】CF1661 C,二分,算法

思路:

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

【二分答案】CF1661 C,二分,算法

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode2560. House Robber IV——二分答案+动态规划

    There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes. The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed. You are given an integer array nums representi

    2024年02月21日
    浏览(35)
  • 【每日一题Day224】LC2517礼盒的最大甜蜜度 | 二分答案

    礼盒的最大甜蜜度【LC2517】 You are given an array of positive integers price where price[i] denotes the price of the ith candy and a positive integer k . The store sells baskets of k distinct candies. The tastiness of a candy basket is the smallest absolute difference of the prices of any two candies in the basket. Return the maximum tastiness of a

    2024年02月07日
    浏览(36)
  • 【洛谷 P1024】[NOIP2001 提高组] 一元三次方程求解 题解(数学+二分答案)

    有形如: a x 3 + b x 2 + c x + d = 0 a x^3 + b x^2 + c x + d = 0 a x 3 + b x 2 + c x + d = 0 这样的一个一元三次方程。给出该方程中各项的系数( a , b , c , d a,b,c,d a , b , c , d 均为实数),并约定该方程存在三个不同实根(根的范围在 − 100 -100 − 100 至 100 100 100 之间),且根与根之差的绝对值

    2024年02月06日
    浏览(36)
  • LeetCode719. Find K-th Smallest Pair Distance——二分答案

    The distance of a pair of integers a and b is defined as the absolute difference between a and b. Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 = i j nums.length. Example 1: Input: nums = [1,3,1], k = 1 Output: 0 Explanation: Here are all the pairs: (1,3) - 2 (1,1) - 0 (3,1) - 2

    2024年01月25日
    浏览(38)
  • Leetcode 第 380 场周赛 Problem C 价值和小于等于 K 的最大数字(Java + 二分答案 + 规律)

    Problem: 100160. 价值和小于等于 K 的最大数字 给你一个整数 k 和一个整数 x 。 令 s 为整数 num 的下标从 1 开始的二进制表示。我们说一个整数 num 的 价值 是满足 i % x == 0 且 s[i] 是 设置位 的 i 的数目。 请你返回 最大 整数 num ,满足从 1 到 num 的所有整数的 价值 和小于等于 k 。

    2024年01月19日
    浏览(41)
  • 【算法】二分查找(整数二分和浮点数二分)

    大家好!今天我们来学习二分查找算法,这是一种效率很高的算法哦! 目录 1. 整数二分 2. 整数二分模板 3. 整数二分模板题 3.1 洛谷 P2249 【深基13.例1】查找 3.2 Acwing789. 数的范围 4. 浮点数二分 5. 浮点数二分模板 6. 浮点数二分模板题 6.1 Acwing 790.数的三次方根 6.2 洛谷 P1024 [

    2024年02月10日
    浏览(52)
  • labview 2020 (2018)调用python报错1663、1662、1661

    写在前面: 本贴适用于解决labview调用python时的1663/1662/1661报错,在网友铝合金蝴蝶的原创帖基础上补充了一些细节,以及必要的文件,步骤详细,可操作性强。 一、1663报错解决办法 labview官方对1663报错的解释: 安装python位数(32/64)与labview位数(32/64)不匹配, labview不支

    2023年04月08日
    浏览(40)
  • 【算法系列篇】二分查找——这还是你所知道的二分查找算法吗?

    在生活中,我们往往会遇到在数组中查找某个确定的元素的时候,通常我们会选择使用暴力解法,这样虽然简单,但是时间复杂度是O(N),时间效率比较低。那么是否有方法可以使得在具有二段性的数组中找某一特定的元素的时间复杂度低于0(N)呢?答案是肯定的,当我们可以

    2024年02月11日
    浏览(52)
  • PPP协议原理介绍+报文分析+配置指导-RFC1661

    个人认为, 理解报文就理解了协议 。通过报文中的字段可以理解协议在交互过程中相关传递的信息,更加便于理解协议。 因此本文将在PPP协议报文的基础上进行介绍。 关于PPP协议基本原理,可参考 RFC1661-The Point-to-Point Protocol (PPP) 。 关于PPP协议的IPv4控制协议,可参考 RFC1

    2024年01月25日
    浏览(41)
  • 【算法】简单的二分查找算法

    一个简单的二分查找算法:         简单描述:算法由静态方法rank()实现,它接受一个整数键和一个有序的int数组作为参数,如果整数存在于数组,返回它的索引,否则返回-1,算法使用两个变量lo和hi,并保证整数如果存在于数组中则它一定存在于a[lo...hi]中,然后通过循

    2024年01月21日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包