题解：B4107 [CSP-X2024 山东] 刷题
yyycj
·
·
题解
题目简述
小红有 n 道编程题，每到编程题需要的时间为 a_{i}。她要在 m 天内按顺序做完所有题目，不能用多天完成同一道题。每天她还可以求助小明 1 道题，求助的这道题省去做题时间。
求她在 m 天内最长做题时间的最小值.
主要思路
首先注意到一种情况：如果 n \le m 也就是题目数小于规定天数，那么她就可以在任意 n 天每天都问 1 道题，这样答案就为 0。
采用算法
暴力搜肯定是想多了，n \le 10^{5}。于是可以采用二分答案的算法，时间复杂度 O(n \log n)。
一开始设定变量 l 和 r，然后每次取中间值，判断这个值是否能成为答案，不断压缩区间，最后一个满足条件的值即为答案就是二分答案的思路。
### 判断是否能成为答案
记录一个 $cnt$ 变量，一开始设为 $1$，用于表示现在是第几天；再记录一个 $sum$ 变量，一开始设为 $0$，用于表示当天的做题时间和；还要记录一个 $maxn$ 变量，一开始设为 $0$，用于表示当天最长做题时间。
遍历 $a_{1} \sim a_{n}$，判断 $sum - maxn + a_{i}$ 是否大于 $mid$。由于答案要求最小，所以一定要问做题时间最长的题在代码中表现出来就是减 $maxn$。
如果大于，则开始下一天，将 $cnt$ 自增 $1$，$sum$ 和 $maxn$ 设为 $a_{i}$；否则，只将 $sum$ 加上 $a_{i}$ 即可。
## AC Code
```cpp
#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 1e5 + 10;
typedef unsigned int ui;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const double PI = acos(-1.0);
typedef unsigned long long ull;
// ----------------------------
// ----------------------------
int a[N];
// ----------------------------
inline int read() {
int f=1,sum=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
return sum*f;
}
void print(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);}
putchar(char(x%10+'0'));
}
bool check(int n,int m,int x) {
int cnt = 1;
int sum = 0;
int maxn = 0;
for (int i=1;i<=n;i++) {
maxn = max(maxn,a[i]);
if (sum-maxn+a[i] > x) {
cnt++;
sum = a[i];
maxn = a[i];
}
else sum += a[i];
}
return cnt <= m;
}
int _find(int n,int m,int r) {
int l = 0;
int ans = 0;
while (l <= r) {
int mid = (l+r) / 2;
if (check(n,m,mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
int main() {
int r = 0;
int n = read();
int m = read();
if (n <= m) {
print(0);
return 0;
}
for (int i=1;i<=n;i++) {
a[i] = read();
r += a[i];
}
// ------------------------
print(_find(n,m,r));
return 0;
}
```
## 后言
本人山东省小学生，有幸参加了 CSP-X2024，这道题在赛场看+想 $15$ 分钟左右，代码 $25$ 分钟左右，最后成功 AC，我甚至觉得挺简单。但是上半场 B 题只拿了 $55$ 就很蒻。