吃糖【二分】

题目描述

Bessie有$N(1≤N≤50,000)$N(1≤N≤50,000)颗糖果，编号$1-N$1−N，但她不打算马上吃光，而是计算在接下来的$D(1≤D≤50,000)$D(1≤D≤50,000)天按糖果编号从小到大逐天吃，当然，$Bessie$Bessie以一天连续吃多颗糖果，也可以不吃，但不能跳着糖果来吃，要按糖果顺序吃。
吃了糖果i，$Bessie's$Bessie′s的能量值会增加$H_i(1≤H_i≤1，000,000)$Hi​(1≤Hi​≤1，000,000)。$Bessie$Bessie都是在白天吃糖果，然后晚上睡觉，第二天醒来，她的能量值会变成前一天的能量值的一半(向下取整)。$Bessie's$Bessie′s的能量值会累加。请你决定第i颗糖果应该是第几天吃，才能使得$Bessie$Bessie在这D个晚上里，能量值最小的那个晚上(假设是第x个晚上)，第$x$x个晚上的能量值最大?输出该值，并且输出第$1(1≤i≤N)$1(1≤i≤N)颗糖果是Bessie第几天吃掉的。
例如：有5个糖果，能量值分别是：$(10，40，13，22，7)。$(10，40，13，22，7)。
$Bessie$Bessie按以下方式吃糖果，将会得到最优值：
第几天 醒来时能量值 吃了糖果后能量值 晚上睡觉能量值
1 0 10+40 50
2 25 ----- 25
3 12 13 25
4 12 22 34
5 17 7 24
可以看出，第1天吃了糖果1、糖果2，第2天不吃糖果，第3天吃了糖果3，第4天吃了糖果4，第5天吃了糖果5。那么在这5个晚上，能量值最低的是第5个晚上，能量值是24，所以输出24。然后你还要输出第$1(1≤i≤N)$1(1≤i≤N)颗糖果是$Bessie$Bessie第几天吃掉的。

输入

第1行：两个整数：$N和D$N和D
第$2-N+1$2−N+1行：每行一个整数$H_i$Hi​.

输出

第l行：一个整数，在这$D$D个晚上里，能量值最小的那个晚上(假设是第$X$X个晚上)，第$x$x个晚上的能量值最大可以是多少?
第$2-N+1$2−N+1行：每行一个整数，第i行表示第i颗糖果是第几天被吃的。

样例输入

5 5
10
40
13
22
7

样例输出

24
1
1
3
4
5

题解：

本题可以用二分答案去解决。当我们知道答案后，贪心地去吃糖果，从左往右扫描糖
果，如果当前的能量没有达到答案，那么必须把当前的那颗糖果吃掉，如果当前的能量已
经达到了答案，那么当天没有必要再吃当前的那颗糖果，留着第二天吃更好。如此扫描下
去，看最后能维持的天数是否达到题目给出的天数d，如果达到，则是可行的，否则是不可行。时间复杂度是O(NlogN)。

#include <bits/stdc++.h> 
#define ll long long
using namespace std; 
const int N=50100;
ll c[N];
int a[N],n,d;
int check(ll x,int flag)
{
    int k=0;
    ll now=0;   
    for(int i=1;i<=d;i++)
    {
        now/=2;
        while(now<x&&k<=n)
        {
            k++;
            if(flag)a[k]=i;
            now+=c[k];
        }
        if(now<x) return 0;
    }
    if(flag)
        for(int i=k+1;i<=n;i++)a[i]=d;
    return 1;
}
int main()
{
    ll ans=0,l=0,sum=0;
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&c[i]);
        sum+=c[i];
    }
    while(l<=sum)
    {
        ll mid=(l+sum)/2;
        if(check(mid,0))
        {
            ans=mid;
            l=mid+1;
        }
        else sum=mid-1;
    }
    printf("%lld\n",ans);
    check(ans,1);  
    for(int i=1;i<=n;i++)
        printf("%d\n",a[i]);
    return 0;
}