洛谷 AT_abc365_c [ABC365C] Transportation Expenses 题解
题目大意
有 N N N 个人，高桥要给这其中的第 i i i 个人 min ( A i , x ) \min(A_i,x) min(Ai,x) 元钱，保证 x ≥ 0 x\ge0 x≥0。
请问在保证高桥给的钱的总数不大于 M M M 的情况下， x x x 的值最大是多少，若 x x x 可以无限大，那么输出 infinite。
题目分析
先考虑 x x x 可以无限大的情况：
- 容易得到高桥给的钱的总数为 ∑ i = 1 n min ( x , A i ) \displaystyle\sum^n_{i=1}\min(x,A_i) i=1∑nmin(x,Ai)，由于 x x x 的值无限大，所以上式可以简化为 ∑ i = 1 n A i \displaystyle\sum^n_{i=1}A_i i=1∑nAi。又因为高桥最多只能给出 M M M 元，所以在 x x x 无限大的时候 ∑ i = 1 n A i \displaystyle\sum^n_{i=1}A_i i=1∑nAi 是小于等于 M M 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 是否小于等于 Mint 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，因为有个库函数也叫 findint 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 就输出 infinitecout << findAns(ma);return 0;
}
AC 记录
AtCoder 记录
注：由于开了完隐就不展示洛谷 AC 记录了。