洛谷 P2985 [USACO10FEB] Chocolate Eating S

题目链接

分析

最小值最大化，很明显的二分答案，且单调性也很明显，如果某个开心值不行，那么更大的开心值一定不行，跟小的一定可以。

所以二分的判断只需模拟 Bessie 吃巧克力的过程即可，若在某时刻没有巧克力可吃则不可行，题目最后还要求输出每个巧克力那天吃，只需在模拟一遍，注意如果有没吃完的巧克力就在最后一天吃完。

代码

#include <bits/stdc++.h>
#define debug puts("Y")
#define inf 0x3f3f3f3f
#define int long long

using namespace std;

const int N = 5 * 1e4 + 5;
int n, d, sum, h[N];

bool check(int x) {//开心值为x是否可行 
	int now = 1, cnt = n, happy = 0;
	for (int i = 1; i <= d; i ++) {
		happy /= 2;
		for (; happy < x;) {
			if (!cnt) {
				return false;
			}
			cnt --;
			happy += h[now ++];
		}
	}
	return true;
}

signed main() {
	cin >> n >> d;
	for (int i = 1; i <= n; i ++) {
		cin >> h[i];
		sum += h[i];
	}
	int l = -1, r = sum + 1;
	for (int mid; l + 1 < r;) {
		mid = (l + r) / 2;
		if (check(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	cout << l << "\n";
	int now = 1, cnt = n, happy = 0;
	for (int i = 1; i <= d; i ++) {
		happy /= 2;
		for (; happy < l;) {
			cout << i << "\n";
			cnt --;
			happy += h[now ++];
		}
	}
	for (; cnt; cnt --) {
		cout << d << "\n";
	}
  return 0;
}