题目： [USACO 2010 Feb S]Chocolate Eating ，哈哈，我们今天来看一道二分答案的题嘛，这是选自USACO上的一道题，好了，我们一起来看看题意吧：
题目描述是复制的，可能有部分显示不对，我就把题目链接放下面！
题目链接： [USACO 2010 Feb S]Chocolate Eating
题目描述
输入描述
- Line 1: Two space separated integers: N and D
- Lines 2…N+1: Line i+1 contains a single integer: Hi
输出描述
- Line 1: A single integer, the highest Bessie’s minimum happiness can be over the next D days
- Lines 2…N+1: Line i+1 contains an integer that is the day on which Bessie eats chocolate i
示例1
输入
5 5
10
40
13
22
7
输出
24
1
1
3
4
5
思路:
这道题我们直接用二分答案的思想来解决，二分最小快乐值，若当天的快乐值达不到，则吃巧克力，若巧克力不够，则当前这个答案大了，不符合题意！具体的看代码，有注释！
我们来看看成功AC的代码吧：
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,d; ll a[100000]; ll l,r; ll ans[100000]; int check(ll x){ ll sum=0,ct=0; for(int i=1;i<=d;i++){//有个坑点就是： 最后一天不能剩巧克力 while(sum<x){ sum+=a[++ct]; if(ct>n) return 0; if(x==l) ans[ct]=i; } sum>>=1; } return 1; } int main(){ ios::sync_with_stdio(false); cin>>n>>d; ll sum=0; for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i]; l=0,r=sum; while(l<r){//二分模板 ll mid=(l+r+1)>>1; if(check(mid)) l=mid; else r=mid-1; } cout<<l<<"\n"; check(l);//这里调用是为了输出巧克力是第几天吃的 for(int i=1;i<=n;i++) if(ans[i])cout<<ans[i]<<"\n"; else cout<<d<<"\n";//输出剩余的巧克力 return 0; }
