题意分析

题目要求将$m$本页数不同的书籍分配给$k$个抄写员，每个抄写员必须分配到连续的书籍序列。目标是最小化最大分配页数，即让工作负担最重的抄写员的工作量尽可能小。若有多个解，则优先使前面的抄写员工作量更小。

关键约束：

• 每本书必须分配给一个抄写员
• 分配必须是连续的
• 每个抄写员至少分配到一本书
• 输出时用'/'分隔不同抄写员的任务

解题思路

1. 二分搜索确定最小最大页数：

   • 最小可能值$min$：单本书的最大页数
   • 最大可能值$max$：所有书的总页数
   • 通过二分法找到满足条件的$mid$值

2. 贪心验证可行性：

   • 从后向前分配书籍，确保每个抄写员的工作量不超过$mid$
   • 若剩余抄写员数量不足，则向前插入分隔符

实现步骤

1. 输入处理：

   • 读取测试用例数$t$
   • 对每个用例，读取$n$（书籍数）和$m$（抄写员数）
   • 读取每本书的页数，计算$min$和$max$

2. 二分搜索：

   • 在$[min, max]$区间内搜索最小$mid$
   • 使用separate()函数验证当前$mid$是否可行

3. 分配方案生成：

   • 从后向前扫描，标记分隔位置
   • 补充分隔符以满足$k$个抄写员的要求

4. 输出结果：

   • 按顺序输出页数
   • 在标记位置插入'/'分隔符

C++实现

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 5005;

ll max, min, num[N];
bool vis[N];
ll m, n;

// 验证是否可以将书籍分割为不超过x的连续块
bool separate(ll x) {
    ll k = 0;
    ll sum = 0;
    for(int i = 0; i < n; i++) {
        if(sum + num[i] <= x) {
            sum += num[i];
        } else {
            k++;
            sum = num[i];
        }
        if(k > m-1) return false;
    }
    return true;
}

// 二分查找最小最大页数
ll bitSearch() {
    ll x = min, y = max, mid;
    while(x < y) {
        mid = x + (y - x)/2;
        if(separate(mid)) y = mid;
        else x = mid + 1;
    }
    return x;
}

int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%lld%lld",&n,&m);
        min = -1;
        max = 0;
        for(int i = 0; i < n; i++) {
            scanf("%lld",&num[i]);
            if(min < num[i]) min = num[i];
            max += num[i];
        }
        
        memset(vis,0,sizeof(vis));
        ll res = bitSearch();
        
        // 从后向前标记分隔位置
        ll sum = 0, k = 0;
        for(int i = n-1; i >= 0; i--) {
            if(sum + num[i] <= res) {
                sum += num[i];
            } else {
                sum = num[i];
                k++;
                vis[i] = true;
            }
        }
        
        // 补充分隔符
        for(int i = 0; i < n && k < m-1; i++) {
            if(!vis[i]) {
                vis[i] = true;
                k++;
            }
        }
        
        // 输出结果
        for(int i = 0; i < n-1; i++) {
            printf("%lld ",num[i]);
            if(vis[i]) printf("/ ");
        }
        printf("%lld\n",num[n-1]);
    }
    return 0;
}

代码说明

1. 核心函数：

   • separate()：验证当前$x$是否可行
   • bitSearch()：二分查找最小$x$

2. 关键变量：

   • min：单本书最大页数（下界）
   • max：总页数（上界）
   • vis[]：标记分隔位置

3. 时间复杂度：

   • 二分查找：$O(\log(\sum p_i))$
   • 验证函数：$O(n)$
   • 总体：$O(n \log(\sum p_i))$

4. 示例分析：

   • 输入9 3和100...900时：
     • 最优解为$1500$（第一抄写员$100+...+500$）
     • 输出100 200 300 400 500 / 600 700 / 800 900