题意#
给定一个长度为 的序列 ，现在要把它划分成 段，问每段平均数的最小值最大能是多少。
精度上，要求误差 .
，.
分析#
要让最小值最大，想到二分答案，但 部分不是很好想。
容易想到时间复杂度较劣的DP做法。
暴力DP#
设 表示，处理完前 个数，分成了 段，每段平均数最小值的最大可能值。
预处理前缀和 ，则有转移方程：
表示 的过程，要和新加入的 的平均值取 .
这样 DP 的时间复杂度为 ，不是很容易继续优化。
二分答案#
假设二分出了一个值 ，需要 其是否可能作为答案。
我们把序列中的每个数都减去 后，一段的平均数 当且仅当这段的元素和 .
在每次 时，先算出数列 ，再对 计算前缀和 。
若序列可以分为 个平均值 的段，则说明在序列 上，以一个 的数为开头，且以 为结尾的最长不下降子序列长度 .
于是问题变成：如何快速求这样的最长不下降子序列。
在求出最长不下降子序列长度之后， 操作就结束了。
最长不下降子序列#
求序列 中，以非负整数开头，以 结尾的最长不下降子序列。
设 表示以 结尾的最长不下降子序列长度，转移显然：
暴力做是 的，可以用树状数组优化到 .
先把点按照权值排序，树状数组以序列原本的下标为下标。
在按权值排序后的序列顺序递推，每次利用树状数组求前缀最大值即可。
代码#
实现的时候先整体 ，用整数计算。不过也可以直接用小数算。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
int n, k, a[MAXN];
class BIT{
private:
int c[MAXN], N = 2e5;
public:
void init(){ memset(c, 0xc0, sizeof(c)); }
inline int lowbit(int x) { return x & (-x); }
inline void update(int x, int w) {
for(; x <= N; x += lowbit(x)) c[x] = max(c[x], w);
}
inline int query(int x) {
int ret = -inf;
for(; x; x -= lowbit(x)) ret = max(ret, c[x]);
return ret;
}
} Bit;
int pos[MAXN];
pair<int, int> s[MAXN];
bool check(int mid) {
int cnt = 0; Bit.init();
s[0] = make_pair(0, 0);
for(int i = 1; i <= n; i++) {
s[i].first = s[i - 1].first + a[i] - mid;
s[i].second = i;
}
sort(s, s + n + 1);
pos[s[0].second] = ++cnt;
for(int i = 1; i <= n; i++) {
if(s[i].first != s[i - 1].first) ++cnt;
pos[s[i].second] = cnt;
}
//求：每个元素都>=0的最长上升子序列长度
Bit.update(pos[0], 0);
for(int i = 1; i < n; i++) {
int ret = Bit.query(pos[i] - 1);
Bit.update(pos[i], ret + 1);
}
return (Bit.query(pos[n] - 1) + 1 >= k);
}
signed main() {
ios::sync_with_stdio(false);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) a[i] *= 10000;
int l = 0, r = 100 * 10000, mid, ans;
while(l <= r) {
mid = (l + r) >> 1;
if(check(mid)) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
cout << ans / 10000.0 << endl;
return 0;
}