题目链接
CSP-X2024山东小学组T4:刷题
题目描述
比赛之路多艰,做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩,小红就是这样的人。
为了继续提升自己的编程实力,小红整理了一份刷题题单,并选中了题单中的 n n n 道编程题,将它们从 1 1 1 到 n n n 编号,计划用 m m m 天时间按照题目编号顺序做完所有的题目(一道题目只能在同一天完成,不可以使用多天完成同一道题目)。
在小红的计划中,她完成第 i i i 道题目的时间为 a i a_i ai。因为题目有难有易,小红做题时可以找好朋友小明帮忙解题,通过询问小明一道题目的解法,可以省去这个题目的做题时间。当然了,小红做题是为了提升自己,而不是提升小明。因此小红决定一天最多求助小明一次。
本题 m m m 天中,小红做题时间最长一天的总耗时定义为 T T T(小明帮忙做的题目不计入小红的做题总时间)。请你帮小红求出 T T T 的最小值是多少?
输入格式
第一行两个正整数 n n n, m m m,分别表示小红要做的题目数和计划用的天数。
第二行 n n n 个正整数,分别表示每个题目解题所用时间 a i a_i ai。
输出格式
输出仅一行,表示 m m m 天中耗时最长一天的总耗时 T T T 的最小值。
样例 #1
样例输入 #1
4 2
1 2 3 3
样例输出 #1
3
样例 #2
样例输入 #2
3 4
999 999 999
样例输出 #2
0
提示
30% 的数据, n ≤ 1000 n \leq 1000 n≤1000;
60% 的数据, n ≤ 10 , 000 n \leq 10,000 n≤10,000;
100% 的数据, n ≤ 100 , 000 n \leq 100,000 n≤100,000, 0 ≤ a i ≤ 10 , 000 0 \leq a_i \leq 10,000 0≤ai≤10,000, 1 ≤ m ≤ 1000 1 \leq m \leq 1000 1≤m≤1000。
算法思想
根据题目描述,要在 m m m天里按顺序完成 n n n道题,并且每天都可以求助小明帮忙解决一道题,求做题时间最长的一天总耗时 T T T的最小值,显然可以用二分查找来解决。
那么如何判断二分的结果 m i d mid mid是否满足要求呢?这里可以用贪心的思想,在一天中做题时间不超过 m i d mid mid的情况下,尽可能的多做题,不妨设 c n t cnt cnt天能把 n n n道题做完,当 c n t ≤ m cnt\le m cnt≤m时满足要求。
除此之外,对于小明来说,显然要去解决每一天中耗时最长的那道题。
时间复杂度
最坏情况下,在 1 1 1天里把所有题做完,那么最小值 T = n × a i T=n\times a_i T=n×ai,那么时间复杂度为: O ( n × l o g T ) O(n\times logT) O(n×logT)
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100005;
int n, m, a[N];
bool check(LL mid)
{int cnt = 1, maxx = a[1]; //统计每天里耗时最长的题目所用时间LL sum = a[1]; //统计一天里做题的总时间for(int i = 2; i <= n; i ++){maxx = max(maxx, a[i]); //求一天里耗时最长的题目所用时间if(sum + a[i] - maxx <= mid) sum += a[i]; //如果一天的做题时间不超过mid,那么就再做一题else{cnt ++; //需要的天数增加sum = a[i]; maxx = a[i];}}return cnt <= m; //当做完n道题的天数不超过时,满足要求
}
int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> a[i];LL L = 0, R = 1e10; //最坏情况在1天把n道题做完,因此R=n*a[i]while(L < R){LL mid = (L + R) / 2;if(check(mid)) R = mid;else L = mid + 1;}cout << L << endl;
}