健身计划（二分答案）

健身计划
时空限制：1s，128MB
题目描述
共有 n 个有顺序的任务，第 i 个任务需要 Ti 的时间，这些任务需要在 k 天内完成。对于每个任务，必须在同一天内完成而不能在两天里分别完成。另外，每一天的任务必须是连续的，比如不能在第一天只完成任务一和任务三而在另一天完成任务二。现在小 Z 很累，他想让你帮忙制定这个计划，使得锻炼时间最长的一天花费的时间最短。方案可能有多种，请任意输出一种即可，采用Special Judge评测。
输入格式：
第一行两个整数 n，k；
第二行 n 个整数，第 i 个整数表示第 i 个任务所需要的时间。
输出格式：
共 k 行，每行两个整数，第 i 行表示在第 i 天需要完成的任务的起始编号和终止编号。这 k行的起始编号应该从小到大排列。
数据规模：n<=100000,1<=k<=n,1<=Ti<=2*10^9
思路：二分答案，注意到它的问法，最长的最短，那必然是二分答案的题目，我们就直接查询最后答案，初始二分查询区间为[1，∑ai]，然后check函数检查可行性，注意这个题可能存在多解。
代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
long long a[100005];
long long b[100005];
long long n,m,i,j,k,maxx;
long long r()
{
    long long ans=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        ans*=10;
        ans+=ch-'0';
        ch=getchar();
    }
    return ans*f;
}

int check(int x)
{
    memset(b,0,sizeof(b));
    long long now=0,nk=1;
    for(i=1;i<=n;i++)
    {
        if(nk-1>=m)
        return 0;
        if(now+a[i]>x)
        now=a[i],b[i]=++nk;
        else
        b[i]=nk,now+=a[i];
    }
    for(i=1;i<=n;i++)
    {
        if(!b[i])
        return 0;
    }
    if(nk==m+1)
    return 0;
    return 1;
}

void erfen()
{
    long long mid;
    long long ll=1,rr=maxx,last=-1;
    while(ll<rr)
    {
        mid=(ll+rr)/2;
        if(!check(mid)) ll=mid;
        else rr=mid-1;
        if(last==mid)
        break;
        else
        last=mid;
    }
    check(mid);
}

int main()
{
    freopen("exercise.in","r",stdin);
    freopen("exercise.out","w",stdout);
//  memset(f,0x7f,sizeof(f));
    n=r(),m=r();
    for(i=1;i<=n;i++)
    a[i]=r(),maxx+=a[i];

    for(j=n;j<=maxx;j++)
    check(j);

    erfen();
    int nn=-1,p=1;
    while(p<=n)
    {
        if(b[p]!=nn)
        {
            if(p==1)
            cout<<p<<" ";
            else
            cout<<p-1<<endl<<p<<" ";
            nn=b[p];
        }
        p++;
    }
    cout<<n;
    return 0;
}
/*
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10
*/

这里写图片描述

健身计划（二分答案）

浏览过的版块