洛谷 P2985 [USACO10FEB] Chocolate Eating S

发布时间:2024年01月24日

题目链接

分析

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

所以二分的判断只需模拟 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;
}
文章来源:https://blog.csdn.net/zc2000911/article/details/135823962
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。