[USACO 2010 Feb S]Chocolate Eating-蒲公英云

[USACO 2010 Feb S]Chocolate Eating

⭐简单说两句⭐

作者：**后端小知识**

CSDN个人主页：后端小知识

?GZH：后端小知识

?欢迎关注?点赞?收藏⭐️留言?

题目： [USACO 2010 Feb S]Chocolate Eating ，哈哈，我们今天来看一道二分答案的题嘛，这是选自USACO上的一道题，好了，我们一起来看看题意吧：

题目描述是复制的，可能有部分显示不对，我就把题目链接放下面！
题目链接： [USACO 2010 Feb S]Chocolate Eating

题目描述

watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16

输入描述

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;
}