[USACO 2010 Feb S]Chocolate Eating

￡神魔★判官ぃ 2024-04-20 07:15 61阅读 0赞

⭐**简单说两句**⭐

> **作者：****后端小知识**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

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

题目描述是复制的，可能有部分显示不对，我就把题目链接放下面！  
题目链接： [\[USACO 2010 Feb S\]Chocolate Eating][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;
    }

【都看到这了，点点赞点点关注呗，爱你们】??

![抽象工厂  引导关注][1caaf89f43f9c2ec5fdddccc50c08a6c.png]

**结语**

`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!???

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

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

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

[Link 1]: https://blog.csdn.net/m0_46833224
[USACO 2010 Feb S_Chocolate Eating]: https://ac.nowcoder.com/acm/problem/24724
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/e4c21cefaa1d4ea3801bc8612400e441.png
[1caaf89f43f9c2ec5fdddccc50c08a6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/913394571fdf44edaf7491da9913852c.png