社区讨论

帮帮我这个60pts的蒟蒻吧~

P2985[USACO10FEB] Chocolate Eating S参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m419lep7
此快照首次捕获于
2024/11/28 20:02
去年
此快照最后确认于
2024/11/28 20:31
去年
查看原帖
CPP
#include<bits/stdc++.h>
#define int unsigned long long
#define N 50005

using namespace std;

int n,d,a[N],l,r,mid,ans = -1,b[N],c[N],t;

bool f(int x)
{
	memset(b,0,sizeof(b));
	int sum = 0;
	t = 1;
	for(int i = 1;i <= d;i++)
	{
		sum /= 2;
		while(sum < x)
		{
			if(t > n)
			{
				return 0;
			}
			b[t] = i;
			sum += a[t];
			t++;
		}
	}
	return 1;
}

signed main()
{
	ios :: sync_with_stdio(0);
	cin >> n >> d;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	l = 1,r = 1e9;
	while(l <= r)			//二分最小开心值 
	{
		mid = l + r >> 1;	// B 数组可能是存的错误答案,样例:3 3 4 6 4 
		if(f(mid))
		{
			ans = mid;
			l = mid + 1;
			for(int i = 1;i <= n;i++)
			{
				c[i] = b[i];
			}
		}
		else
		{
			r = mid - 1;
		}
	}
	cout << ans << endl;
	
	for(int i = 1;i <= n;i++)
	{
		cout << c[i] << endl;
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...