题目描述

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

经过探测，深海中一共有 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;
}