题解 | 整点巧克力

#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int* a = new int[n + 1];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	} 
  	//注意二分的右边界，一开始想错了以为m = n那么r不会超过1e7，但是当m远小于n时r的右边界最大会到m * n
	long long l = 1, r = 1e11;
	int* eat = new int[n + 1];
	while (r > l) {
		long long mid = (r - l) / 2 + l;
		//第几块巧克力 
		int j = -1, days = 0;
		long long cnt = 0;
		while (j < n) {
			cnt >>= 1;
			while (j < n && cnt < mid) {
				j++;
				cnt += a[j];
			}
			if (j < n) days++;
		}
		if (days >= m) l = mid + 1;
		else r = mid;
	}
  	//二分过程中保留eat[]会出现因为mid = left + 1而导致存储错误的结果
	int j = -1, days = 0;
	long long cnt = 0;
	while (j < n) {
		cnt >>= 1;
		while (j < n && cnt < l - 1) {
			j++;
			eat[j] = min(days + 1, m);
			cnt += a[j];
		}
		if (j < n) days++;
	}
	cout << l - 1 << endl;
	for (int i = 0; i < n; i++) {
		cout << eat[i] <<endl;
	}
}