题解 | #Chocolate Eating#

Chocolate Eating

题目描述：

Bessie has received N (1 <= N <= 50,000) chocolates from the bulls, but doesn't want to eat them too quickly, so she wants to plan out her chocolate eating schedule for the next D (1 <= D <= 50,000) days in order to maximize her minimum happiness level over the set of those days.
Bessie's happiness level is an integer that starts at 0 and halves (rounding down if necessary) over night as she sleeps. However, when she eats chocolate i, her happiness level increases by integer HiH_iHi​ (1 <= HiH_iHi​ <= 1,000,000). If she eats chocolates on a day, her happiness for that day is considered the happiness level after she eats the chocolates. Bessie insists that she eat the chocolates in the order that she received them.
If more than one optimal solution exists, print any one of them.
Consider a sequence of 5 chocolates to be eaten over a period of 5 days; they respectively bring happiness (10, 40, 13, 22, 7).

If Bessie eats the first chocolate (10 happiness) on the first day and then waits to eat the others, her happiness level is 10 after the first day.

题意：

贝西从bulls那里收到了N块巧克力。
她不想把它们马上吃完，而是打算制定一个计划，使得在接下来的D天里，使得每天的最小快乐值最大。
贝西的快乐指数可以用一个整数来衡量，一开始的时候是0，当她每天晚上睡觉的时候，快乐指数会减半（奇数时向下取整）。贝西把她的巧克力按照收到的时间排序，并坚持按照这个顺序来吃巧克力。当她吃掉第i块巧克力的时候，她的快乐指数会增加Hj。她那天的快乐值被认为是她吃完巧克力后的快乐水平。每天可以吃任意多块巧克力，如何帮助贝西合理安排，使得D天内她的最小快乐指数最大呢？

思路：

很明显，最小的快乐值最大，得二分

所以我们去二分最小快乐值

最后需要再check一下答案，来记录吃巧克力的天数

那么如何写check函数？

就用循环去跑天数，用sum记录快乐值，如果这一天的sum小于x，就循环去加上接下来的快乐值，直到sum > x时 ，就可以结束这一天，也就是让sum/2。如果len > n，也就是快乐都加没了他还不满足此时的x，就说明快乐值太大了，所吃的不能满足，就得往左缩缩，反之如果全跑完都没问题，就得往右缩缩

坑点！！！

巧克力要全部吃完！

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

ll n, m, len, k, sum;
ll ans[MAX];
ll tr[MAX];

bool check(ll x){
    len = 0;sum = 0;
    for(int i = 1; i <= m; ++i){
        while (sum < x) {
            sum += tr[++len];
            if(len > n)return false;
            if(x == k)ans[len] = i;
        }
        sum /= 2;
    }
    return true;
}

int main(){
    n = IntRead(); m = IntRead();
    for(int i = 1; i <= n; ++i)tr[i] = IntRead();
    ll l = 1, r = 1e12;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if(check(mid))l = mid + 1;
        else r = mid - 1;
    }
    k = l - 1;
    cout<<k<<endl;
    check(k);
    for(int i = 1; i <= n; ++i){
        if(ans[i])cout<<ans[i]<<endl;
        else cout<<m<<endl;
    }
    return 0;
}