编辑代码

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define T 10000
#define K 10000
int a[T];
int b[K];// 记录每人任务时间
int c[K][2]; //[每人][起点+终点]
int l,r,ans;
int t,k;
int max(int a, int b) {
  return (a >= b) ? a : b;
}
bool check(int u){// u秒可不可以由k个人完成
    int s = 1;// 记录当前的人
    //b[N] = {0};
    memset(b, 0, sizeof(int) * k);//初始化数组必须有
    for(int i = 1;i <= t;i++){// 遍历t个任务
        if(b[s] + a[i] > u){// 如果当前时间加上当前任务的时间大于u
            s++;// 选下一个人
            b[s] += a[i];
        }else{
            b[s] += a[i];
        }
    }
    if(s > k){
        return false;
    }
    return true;
}
void print(int u){// u为时间 这是已经确定好时间，坐等输出了
    int i = k,temp = 0;//人是从后往前分配
    for(int j = t;j>0;j--){//任务也是从后往前
        if(c[i][1] == 0){//如果结束任务是0，那么就让这个人的结束任务为j,因为刚给她分配
            c[i][1] = j;
        }
        if(temp + a[j] > u){// 时间超出，则换人（从后往前i--）
            c[i][0] = j + 1;//因为当前j对应的任务加上后就会超出时间，而j是从后向前走的，所以要当前这个人的任务的开始其实应该是之前的j，所以j+1
            i--;//换人
            temp = a[j];//暂存这个需要加到前一个人(新的人)的任务
            c[i][1] = j;//当前的j，换人后的新j（结束坐标）
        }else{
            temp += a[j];
        }
    }
    c[i][0] = 1;
    for(int i = 1;i<=k;i++){
        if(c[i][0] == 0){
            printf("0 0");
            printf("\n");
        }else{
            printf("%d %d",c[i][0],c[i][1]);
            printf("\n");

        }
    }

}
int main () {
    //JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。
    l = -1;r = 0;ans = 0; 
    scanf("%d %d",&t,&k);//t为任务数，k为组员数
    for(int i = 1;i<=t;i++){
        scanf("%d",&a[i]);//第i个整数表示完成第i个任务所需的时间
        l = max(l,a[i]);
        r += a[i];
    }
    while(l<=r){
        int mid = (l + r)/2;
        if(check(mid)){
            r = mid - 1;
            ans = mid;
        }else{
            l = mid + 1;
        }
    }
    print(ans);
    return 0;
}