首页 > 其他分享 >1762F(二分)

1762F(二分)

时间:2022-11-22 01:45:04浏览次数:55  
标签:二分 return cout int sum mid 1762F

题目链接·

思路:

这题用到了一下二分的应用,嗨,当时确实没有想到。可知k是递增的关系。二分判断就可。

AC代码:

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 2e5 + 10;
int a[N];
int n, c, d;
int sum[N];
bool cmp(int a, int b)
{
	return a > b;
}

bool check(int k)
{
	int sum = 0;
	for (int i = 1; i <= min(n, k + 1); i ++ )
	{
		sum += a[i] * (d / (k + 1) + ((d % (k + 1) + 1) > i));
	}

	return sum >= c;
}

void solved()
{
	cin >> n >> c >> d;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + a[i];
	if (a[1] * d < c)
	{
		cout << "Impossible\n";
		return ;
	}
	if (sum[min(n, d)] >= c)
	{
		cout << "Infinity\n";
		return ;
	}

	
	int l = 0, r = d + 1;
	while (l < r)
	{
		int mid = (l + r + 1) >> 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}

	cout << l << '\n';

}

signed main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t -- )
	{
		solved();
	}
	return 0;
}

 

标签:二分,return,cout,int,sum,mid,1762F
From: https://www.cnblogs.com/msluli/p/16913939.html

相关文章

  • 二分查找算法
    是一种针对有序集合的查找算法在python中,有一个模块与之密切相关,就是bisect1importbisect234deffunc():5a=[1,5,9]6bisect.insort(a,6......
  • 整体二分
    动态第k大,第k小,离线下来。考虑第k小怎么求,二分一个数值,然后扫一遍有多少小于等于\(mid\)的。一次nlogn,多次\(n^2log\),既然你的是我的,我的就是你的,你做的就是我做的,我做......
  • 代码随想录刷题营day1|704.二分查找 34. 有序数组找首位末位 35.搜索插入的位置 27.移
    一、数组理论基础数组下标都是从0开始的数组内存空间的地址是连续的数组的元素是不能删的,只能覆盖二、刷题第一题704.二分查找题目链接:https://leetcode.com/prob......
  • 二分查找
    在单调递增序列a中查找>=x的数中最小的一个(即x或x的后继)while(l<r){intmid=(l+r)/2; if(a[mid]>=x) r=mid; elsel=mid+1; }returna[l];在单调递......
  • 二分图相关知识+染色法+匈牙利
    一、相关概念:1、二分图把图中的点分到两个集合中,集合内的点之间没有边相连,边存在于两个集合之间2、匹配、最大匹配、完美匹配匹配:匹配是边的集合,任意两条边都没有公共......
  • 力扣704(java&python)-二分查找(简单)
    题目:给定一个 n 个元素有序的(升序)整型数组 nums和一个目标值 target ,写一个函数搜索 nums 中的target,如果目标值存在返回下标,否则返回-1。示例1:输入:nums......
  • 整体二分
    感谢Sentoayaka姐姐的帮助,没有她就没有这篇文章。我爱神里凌华❥引入这是一道主席树板子:https://www.luogu.com.cn/problem/P3834给你一个长为\(n\)数组\(a\)和......
  • 792. 匹配子序列的单词数 ----- find()暴力、队列分桶查询、二分法哈希
    给定字符串s 和字符串数组 words,返回  words[i] 中是s的子序列的单词个数 。字符串的子序列是从原始字符串中生成的新字符串,可以从中删去一些字符(可以是none)......
  • 代码随想录day1---LeetCode704二分查找&27移除元素
    LeetCode704二分查找[https://leetcode.cn/problems/binary-search/]题目:给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的......
  • 二分搜索算法
    目录介绍基本的二分搜索思路代码实现:查找左边界的二分搜索思路代码实现:查找右边界的二分搜索思路代码实现:介绍二分查找适用于已经排序的序列,通过对搜索区间折半的方式查......