备份比赛数据【算法赛】

0备份比赛数据【算法赛】 - 蓝桥云课

问题描述

蓝桥杯大赛的组委会最近遇到了一个棘手的问题。他们有 N 台电脑需要备份比赛数据，每台电脑所需的备份时间分别为 A1​,A2​,…,AN​ 分钟。

备份必须按编号顺序依次进行，即先第 1 台，再第 2 台，依此类推。每台电脑的备份需要工作人员持续操作，且必须安排在同一天内完成。例如，如果某台电脑的备份需要 5 分钟，那这 5 分钟必须安排在同一天，不能拆分到两天。如果当天剩余时间不足以完成某台电脑的备份，那就只能推迟到第二天进行。

每台电脑备份完成后，系统需要等待 B1​ 分钟才能开始下一台的备份。这段等待时间不需要工作人员操作，且可以跨天进行。例如，如果第 1 台电脑的备份只需在第 2 天开始后等待 10 分钟就能进行。

现在，组委会希望尽量缩短每天的工作时间，以便工作人员尽早下班休息。但上级有要求，所有电脑的备份必须在最多 T 天内完成。对此，请你帮助蓝桥杯组委会计算出每天最少需要安排的工作时间 M（M 最大不可超过 3600），以便所有电脑的备份能在 T 天内顺利完成。如果无论如何都无法满足条件，请直接输出 -1。

输入格式

第一行包含两个整数 N 和 T（1≤N,T≤105），分别表示电脑的数量和最多允许的天数。

第二行包含 N 个整数 A1​,A2​,…,AN​，表示每台电脑的备份时间。

第三行包含 N 个整数 B1​,B2​,…,BN​（1≤Bi​≤3600），表示每台电脑备份完成后需要等待的时间。

输出格式

输出一个不超过 3600 的整数 M，表示每天最少需要安排的工作时间，以确保所有电脑的备份任务能在 T 天内完成。若无法满足条件，则输出 -1。

样例输入

3 2
1 2 3
2 2 2

样例输出

5

样例说明

每天工作时间为5分钟时，备份任务将按以下方式进行：

• ​第1天：​

  • 第1台电脑的备份需要1分钟（第0~1分钟）。
  • 等待 B1​=2 分钟（第1~3分钟）。
  • 第2台电脑的备份需要2分钟（第3~5分钟）。

• ​第2天：​

  • 等待 B2​=2 分钟（第0~2分钟）。
  • 第3台电脑的备份需要3分钟（第2~5分钟）。

所有备份任务可在2天内完成。

思路：

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5; // 最大电脑数量+5的缓冲int N, T; // 电脑数量和允许的最大天数
int a[MAXN], b[MAXN]; // a存储备份时间，b存储等待时间/*** 检查给定每日工作时间M是否满足T天完成所有备份的条件* @param M 候选的每日工作时间* @return 是否满足条件*/
bool check(ll M) 
{// 预检查：如果有任意备份时间超过M直接不可行for (int i = 1; i <= N; ++i) {if (a[i] > M) // 备份时间超过单日容量{return false;}}ll prev_end = 0; // 上一个备份的结束时间（绝对时间）ll prev_B = 0;   // 上一个备份后的等待时间（初始为0）ll max_day = 0;  // 记录过程中的最大天数// 遍历所有电脑进行备份模拟for (int i = 1; i <= N; ++i) {// 计算当前备份的开始时间 = 前一个结束时间 + 前一个的等待时间ll s_i = prev_end + prev_B; // 计算所在天数：总时间除以每日时长向下取整ll d_i = s_i / M;           // 计算当前天的结束时间：下一天开始前的时间点ll day_end = (d_i + 1) * M; ll current_day; // 当前备份实际所在天数ll end_i;       // 当前备份的结束时间// 判断能否在当天完成if (s_i + a[i] <= day_end) {// 当天可完成：结束时间直接累加end_i = s_i + a[i];current_day = d_i;} else {// 需要跨天：天数+1，结束时间在下一天的开始时刻+备份时间current_day = d_i + 1;end_i = current_day * M + a[i];}// 更新最大天数（注意天数从0开始计数）if (current_day > max_day){max_day = current_day;}// 保存当前备份的结束时间和产生的等待时间prev_end = end_i;prev_B = b[i]; // 记录当前备份后的等待时间（给下一个备份用）}// 最终天数计算：max_day是最后一个备份所在天数，实际需要+1天（天数从0计数）// 例如：max_day=0 表示第1天完成return (max_day + 1) <= T; 
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); // 加速输入输出// 读取输入cin >> N >> T;for (int i = 1; i <= N; ++i) {cin >> a[i];}for (int i = 1; i <= N; ++i) {cin >> b[i];}// 二分查找初始化（左开右闭区间）ll left = 0;      // 不可行下界ll right = 3601;  // 可行上界（包含3600）ll ans = -1;      // 最终结果// 特殊二分模板：寻找第一个可行的Mwhile (left + 1 != right) {ll mid = (left + right) / 2;if (check(mid)) {// 当前mid可行，尝试寻找更小的解right = mid; // 移动右边界} else {// 当前mid不可行，需要增大left = mid; // 移动左边界}}// 结果处理（注意边界）if (right <= 3600) {cout << right << endl;} else {cout << -1 << endl; // 无解或超出限制}return 0;
}