题目描述
小智在刚刚结束的 CET-4 考试中顺利通过了！现在，他要开始备战 CET-6 了。
可是，他的单词功底太差了，于是他准备开始摆烂背单词。
可是，人脑的能力是有限的，小智的大脑每一天都会有一个记忆的上限，如果超过这个上限，再多的单词也记不下了。
有一天，小智在背单词的时候想到了一个问题，你能帮帮他吗？
小智一共有?n?个单词需要背，第?ii?个单词所拥有的「精神值」为?。
小智每天的记忆力都是有上限?mm?的。如果小智在第?ii?天内背完了?[l,r]内的单词，那么这些单词将会占用小智??的记忆力。
小智需要在最多?kk?天里把这些单词全部背完，他希望你在把这些单词背完的同时，让他每天需要的记忆力的最大值尽可能小。
形式化地，你需要将一个序列最多分为?k段，请你找到一个最小的?m，使得1≤i≤k，。
输入格式
第一行有两个整数?n,k，表示小智需要背的单词数量和小智需要背完单词的天数。
第二行有?n?个整数?，第?i?个整数表示第?i?个单词的「精神值」。
输出格式
共一行。
输出一个整数?m，表示小智所需的最小记忆力。
输入输出样例
输入?
5 1 1 2 3 4 5
输出?
55
输入?
4 2 1 2 3 4
输出?
16
说明/提示
样例 1 解释
由于小智最多要在 1 天内背完单词，所以必须将这些单词一次性背完，代价为?55。
样例 2 解释
可以发现，当小智第 1 天背?[1,3] 的单词，第 2 天背?[4,4]?的单词时需要的记忆力最少，为?4^2 = 16。
数据规模与约定
对于所有测试点，保证?1≤n≤1×105，1≤k≤n，1≤ai?≤1×106。
分析
题目要求我们找到最小的m，使得被划分的k个部分的Ci都小于等于m，那么理所当然大于m的所有数x同样满足这个条件，并且划分的组数t可能等于k，也有可能小于k；而小于m的数x划t一定会大于k，所以我们发现m这个答案存在单调性，那就可以使用二分方法来找m，而这个判断的标准就是划分的组数t大于k还是小于等于k，即使等于k也要考虑m再小一点能不能一样满足。
具体流程就是从左往右遍历数列，用sum记录当前组的和，如果下一个数加进来大于x，那么这个数就要另成一组。以这种方式确定x下的分组数k。
这里我们就知道一个数x对应了所分的组数t，我们要求的m就是当t=k时的最小x
Code
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
ll a[N];
int n, k;
bool check(ll x)
{
ll t = 0;
for (int i = 0; i < n; i++)
{
ll sum = a[i];
while (i + 1 < n && sum + a[i + 1] <= x)
sum += a[++i];
if (++t > k)
return false;
}
return true;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> a[i];
a[i] *= a[i];
}
sort(a, a + n);
ll l = a[n - 1];
ll r = 1ll << 60;
ll ans = 0;
while (l <= r)
{
ll mid = (l + r) >> 1;
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
cout << ans << endl;
return 0;
}