【二分】[USACO 2010 Feb S]Chocolate Eating

https://ac.nowcoder.com/acm/contest/22353/E
有的时候50%通不过真的很无助orz

二分查找最小幸福值： 我们希望找出一个最大的 mid，即最小幸福值，使得 Bessie 能够在 d 天内吃完巧克力，并且每天的幸福值都不低于这个 mid。

我们可以通过二分查找的方式来确定这个 mid。mid 的初始范围是 [0, 1e12]，因为幸福值可能很大。
每次我们计算出 mid 的值后，使用 check() 函数来验证是否能够在 d 天内满足每天的幸福值都不低于 mid。如果可以，我们尝试增大 mid；如果不行，我们尝试减小 mid。

注意 如果有剩余巧克力，需要分配到最后一天，不能有剩余

1. 设定二分查找的上下界 low = 0, high = 1e12
2. 进行二分查找：
   a. 计算 mid = (low + high) / 2
   b. 使用 check(mid) 判断是否可以分配巧克力：
   - 如果可以满足最小幸福值为 mid，更新结果，并尝试更大的 mid（low = mid + 1）
   - 如果不可以满足，尝试更小的 mid（high = mid - 1）
3. 输出二分查找的结果（最大最小幸福值）
4. 输出巧克力的分配方案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll n, d;
ll a[50050], happiness[50050], ans[50010];int check(ll mid) {ll i, j, count, sum, tmp[50010];count = sum = 1;happiness[1] = 0;for(i = 1; i <= d; i++) {while(happiness[i] < mid) {if(count > n) return -1;  // 巧克力吃完了，返回 -1tmp[count] = i;  // 记录巧克力被吃掉的天数happiness[i] += a[count++];  // 增加当前天的幸福值}happiness[i + 1] = happiness[i] / 2;  // 下一天的幸福值是前一天的一半}for(i = 1; i < count; i++) ans[i] = tmp[i];  // 记录巧克力的分配天数for(i = count; i <= n; i++) ans[i] = d;  // 剩余巧克力分配到最后一天return 1;
}int main() {cin >> n >> d;for(int i = 1; i <= n; i++) cin >> a[i];ll l = 0, r = 1e12;ll result = 0;// 二分查找寻找最大的最小幸福值while(l <= r) {ll mid = (l + r) >> 1;if(check(mid) == 1) result = mid, l = mid + 1;else r = mid - 1;}cout << result << endl;for(int i = 1; i <= n; i++) cout << ans[i] << endl;
}