网课：第四章二分、三分、01分数规划---[USACO 2010 Feb S]Chocolate Eating

本文主要是介绍网课：第四章二分、三分、01分数规划---[USACO 2010 Feb S]Chocolate Eating，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

贝西收到了N（1 <= N <= 50,000）块巧克力，但她不想吃得太快，因此她想为接下来的D（1 <= D <= 50,000）天制定巧克力食用计划，以便在那些天中最大化她的最低幸福水平。 贝西的幸福水平是一个整数，起始值为0，在夜间睡觉时减半（如果必要的话向下取整）。然而，当她吃掉第i块巧克力时，她的幸福水平增加了整数 Hi （1 <= Hi <= 1,000,000）。如果她在一天中吃了巧克力，她当天的幸福被认为是她吃巧克力后的幸福水平。贝西坚持按照她收到的顺序吃巧克力。 如果存在多个最优解，打印其中任何一个。 将一系列5块巧克力视为在5天内食用的一段时间; 它们分别带来幸福（10、40、13、22、7）。 如果贝西在第一天吃第一块巧克力（10幸福）然后等待吃其他的，那么她在第一天后的幸福水平是10。

 

输入

第1行：两个用空格分隔的整数：N 和 D

第2行到第N+1行：每行包含一个整数： Hi

5 5 
10 
40 
13 
22 
7

输出

第1行：一个整数，贝西在接下来的D天内最高的最小幸福水平

第2行到第N+1行：每行包含一个整数，表示贝西吃掉巧克力i的日期

24
1
1
3
4
5

做法

最小值最大，典型的二分答案。

#include<bits/stdc++.h>
using namespace std;
int n,d;
int isleft(long long num,vector<int> &v){long long res=0;int cnt=0;for(int i=1;i<=d;i++){while(res<num&&cnt<n){res+=v[cnt++];}if(res<num) return 0;res/=2;}return 1;
}
int main(){scanf("%d%d",&n,&d);vector<int> v(n);//开心值vector<int> g(n);long long sum=0;//总开心值for(int i=0;i<n;i++){scanf("%d",&v[i]);sum+=v[i];}long long l=-1,r=sum+1;while(l+1<r){long long mid=l+(r-l)/2;if(isleft(mid,v)) l=mid;else r=mid;}long long res=0;int cnt=0;cout<<l<<endl;for(int i=1;i<=d;i++){while(res<l&&cnt<n){g[cnt]=i;res+=v[cnt++];}res/=2;}for(int i=0;i<n;i++) {if(g[i])cout<<g[i]<<endl;else cout<<d<<endl;//没吃完}}

wa的原因

1.弄错了题意，isleft函数的条件写错了

2.没开long long

3.没关注到巧克力没吃完的情况，有想到，但后面没怎么管，看题解才发现真有这种情况

这篇关于网课：第四章二分、三分、01分数规划---[USACO 2010 Feb S]Chocolate Eating的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---