题目描述

皮皮最近对于环保非常关注，他了解到深海里有很多很多垃圾，因此准备去深海开展一项垃圾清除活动。

经过探测，深海中一共有 n 个区域，环卫队会对所有区域都同时开展清理，清理速度为每秒 a 千克， 每一个区域的垃圾在清理 $t_i$秒后就会被清理干净。

为了达成清理 $M$ 千克垃圾的目标，请问环保人员最少需要在海里清理多久？

【输入格式】

输入共 2 行：
第 1 行：3 个空格隔开的正整数，分别为 n, M, a, 分别代表区域数量，清理垃圾的目标重量，每秒清理垃圾的重量。
第 2 行：n 个空格隔开的正整数，分别表示每个区域需要清理的时间。

【输出格式】

输出共 1 行
第 1 行：1 个整数，表示最少需要清理的时间

【输入输出样例#1】

输入#1

5 100 5
20 5 2 4 8

输出#1

5

【数据范围】

$1\le n\le 10^6,1\le t_i\le 10^7,1\le a\le 100.$输入保证一定能清理 M 千克的垃圾

【代码示例】

#include <bits/stdc++.h>
using namespace std;
int n, m, a, c[1000005];

bool chk(int x) {
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		if (c[i] >= x) {
			sum += x * a;
		} else {
			sum += c[i] * a;
		}
	}
	return sum >= m;
}

int main() {
	cin >> n >> m >> a;
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	int l = 1, r = 1e7, ans = -1;

	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (chk(mid)) {
			r = mid - 1;
			ans = mid;
		} else
			l = mid + 1;
	}
	cout << ans << endl;
}

题目描述

由于对计算机科学的热爱，以及有朝一日成为 「Bessie 博士」的诱惑，奶牛 Bessie 开始攻读计算机科学博士学位。经过一段时间的学术研究，她已经发表了 N 篇论文（1≤N≤105），并且她的第 i 篇论文得到了来自其他研究文献的 ci​ 次引用（0≤ci​≤105）。

Bessie 听说学术成就可以用 h 指数来衡量。h 指数等于使得研究员有至少 h 篇引用次数不少于 h 的论文的最大整数 h。例如，如果一名研究员有 4 篇论文，引用次数分别为 (1,100,2,3)，则 h 指数为 2，然而若引用次数为 (1,100,3,3) 则 h 指数将会是 3。

为了提升她的 h 指数，Bessie 计划写一篇综述，并引用一些她曾经写过的论文。由于页数限制，她至多可以在这篇综述中引用 L 篇论文（0≤L≤105），并且她只能引用每篇她的论文至多一次。

请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 h 指数。

注意 Bessie 的导师可能会告知她纯粹为了提升 h 指数而写综述存在违反学术道德的嫌疑；我们不建议其他学者模仿 Bessie 的行为。

输入格式

输入的第一行包含 N 和 L。

第二行包含 N 个空格分隔的整数 c1​,…,cN​。

输出格式

输出写完综述后 Bessie 可以达到的最大 h 指数。

输入输出样例

输入 #1

4 0
1 100 2 3

输出 #1

2

输入 #2

4 1
1 100 2 3

输出 #2

3

说明/提示

样例解释 1

Bessie 不能引用任何她曾经写过的论文。上文中提到，(1,100,2,3) 的 h 指数为 2。

样例解释 2

如果 Bessie 引用她的第三篇论文，引用数会变为 (1,100,3,3)。上文中提到，这一引用数的 h 指数为 3。

测试点性质

• 测试点 1−7 满足 N≤100。
• 测试点 8−10 满足 N≤1000。
• 测试点 11−17 满足 N≤105。

【代码示例】

#include <bits/stdc++.h>
using namespace std;
int n, m, c[100005];

bool chk(int x) {
	int sum = 0;
	int mm = m;
	for (int i = 1; i <= n; i++) {
		if (c[i] >= x)
			sum++;
		if (c[i] == x - 1 && mm > 0) {
			sum++;
			mm--;
		}
	}
	return sum >= x;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	//if(m<=n) c[n+1]=m;
	//else c[n+1]=n;
	int l = 1, r = 1e5, ans = -1;

	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (chk(mid)) {
			l = mid + 1;
			ans = mid;
		} else
			r = mid - 1;
	}
	cout << ans << endl;
}