洛谷 AT_abc365_c [ABC365C] Transportation Expenses 题解

题目大意

有 $N$ 个人，高桥要给这其中的第 $i$ 个人 $min(A_i,x)$ 元钱，保证 $x\ge0$ 。

请问在保证高桥给的钱的总数不大于 $M$ 的情况下， $x$ 的值最大是多少，若 $x$ 可以无限大，那么输出 infinite。

题目分析

先考虑 $x$ 可以无限大的情况：

容易得到高桥给的钱的总数为 $\displaystyle\sum^n_{i=1}\min(x,A_i)$ ，由于 $x$ 的值无限大，所以上式可以简化为 $\displaystyle\sum^n_{i=1}A_i$ 。又因为高桥最多只能给出 $M$ 元，所以在 $x$ 无限大的时候 $\displaystyle\sum^n_{i=1}A_i$ 是小于等于 $M$ 的。

对于其余情况，只需要二分查找即可。

Code

//请不要抄袭代码
//本代码中变量与题目中的不一样，例如大写 M 在这里是小写 m，需要注意
#include <iostream>
#define int long long//不开 long long 见祖宗
using namespace std;
int n, m, arr[200000];
bool chk(int x) {//判断 x 是否小于等于 M
	int cnt = 0;
	for (int i = 0; i < n && cnt <= m/*当当前花费已经大于 M 时就退出*/; ++i) cnt += min(x, arr[i]);
	return cnt <= m;
}
int findAns(int ma) {//二分函数，这里不推荐函数名写 find，因为有个库函数也叫 find
	int l = 0, r = ma - 1;//二分的右边界为 A 中的最大值减 1，因为只有此时才能减少花费
	while (l <= r) {
		int mid = (l + r) / 2;
		if (chk(mid)) l = mid + 1;//当当前 x 的值不大于 M 时就更新左边界
		else r = mid - 1;//反之则更新右边界
	}
	return r;//返回答案
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int cnt = 0, ma = 0;
	for (int i = 0; i < n; ++i) cin >> arr[i], cnt += arr[i], ma = max(ma, arr[i]);//累加数组和，计算数组最大值
	if (cnt <= m) return cout << "infinite", 0;//若 A 数组元素和小于等于 M 就输出 infinite
	cout << findAns(ma);
	return 0;
}