刷题记录:牛客NC24724[USACO 2010 Feb S]Chocolate Eating

传送门:牛客

输入:
5 5 
10 
40 
13 
22 
7 
输出:
24
1
1
3
4
5

首先这是一道比较容易看出解法的一道二分答案题,即使是check函数的部分也并不难以实现,可以说是一道简单题,但是由于有比较多的注意点(坑点),这道题的难度可以说可以上一个档次

注意点:

1.首先我们需要注意数据的范围,此题需要开long long,但是题目中很难注意到这一点

2.开启long long 之后你还需要注意到即使我们的巧克力已经满足前前几天的要求了,但是我们还有一些剩余的巧克力,此时我们需要将剩余的巧克力都放入最后一天的部分中

3.即使你已经注意到了以上的两点,你还是不能完美的完成这道题,假如你的代码和我的差不多的话

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
ll N,D;
ll a[maxn];
ll day[maxn];
ll check(ll mid) {
	ll sum=0;ll num=1;
	for(int i=1;i<=D;i++) {
		while(sum<mid) {
			if(num>N&&sum<mid) return false;
			sum+=a[num];
			day[num]=i;
			num++;
		}
		sum/=2;
	}
	while(num<=N) {
		day[num]=D;
		num++;
	} 
	return true;
}
int main() {
	N=read(),D=read();
	memset(day,0,sizeof(day));
	ll l=0,r;
	for(int i=1;i<=N;i++) {
		a[i]=read();
		r+=a[i];
	} 
	ll ans;
	while(l<=r) {
		ll mid=(l+r)>>1;
		if(check(mid)) {
			ans=mid;
			l=mid+1;
		}else {
			r=mid-1;
		}
	}
	cout<<ans<<endl;
	for(int i=1;i<=N;i++) printf("%lld\n",day[i]);
	return 0;
}

如果你碰到了这个问题,但是你看了好几遍代码依旧很难找到bug,感觉已经很完善了,那么我在这里提醒一下,因为你保存每个巧克力的时间时是无论mid是否合法都一律进行保存的,也就意味着你最后的时间数组其实可能并不是你的答案的时间数据,需要在输出之前再跑一边check函数即可





毕