这道题目比赛的时候做了半天，结果基本就是挂机的状态。事后看了题解也是一脸懵逼的。最后看了标程才知道怎么做的。看懂之后才发现这个这个题目那么有趣，真是思维太巧妙了（吐槽一下多校赛题解，只有做出了的人才能看懂。（ㄒｏㄒ））。 他是这样解决的二分枚举答案，对于答案如果成立那么一定存在size(l, r)/(r-l+1) < = mid.所以化简得到size(l, r) + l * mid <= (r + 1) * mid. 如何在快速的解决这个呢？就是要用到线段树，首先初始化整个树的时候每个节点保存的是mid * l的值，然后取枚举右边界ｒ。对于每个枚举的ｒ的这种状态下，线段树(L, R)中存放的是,左区间在(L, R) 中，右区间为ｒ的元素种类＋l*mid的最小值。当ｒ增加到ｒ＋１的时候（在处理的时候会有一个app数组记录当前元素出现的上一个位置），对于整个线段树的影响就是当前位置与当前元素出现的上一位置，这个区间加１。 对于二分的时间复杂度为logn，枚举右端点为ｎ，对于每次枚举都要一次区间修改操作是logn,一次查询操作 logn.所以一共为ｏ(n * logn * logn). 代码如下：
#include <iostream> #include <stdio.h> #include <cstring> #include <algorithm> using namespace std; #define Max_N (6*10000+100) double v[4*Max_N]; int addv[4*Max_N]; int n; int a[Max_N]; double min1 ; void build(int node, int l, int r, double m) { v[node] = m * l; addv[node] = 0; if (l == r) return; int m1 = l + (r - l) / 2; build(node*2, l, m1, m); build(node * 2 + 1, m1 + 1, r, m); } int add1(int node, int x) { v[node] += x; addv[node] += x; } void pushdown(int node) { if (addv[node]) { add1(node * 2, addv[node]); add1(node * 2 + 1, addv[node]); } addv[node] = 0; } void change(int node, int l, int r, int y1, int y2) { if (y1 <= l && r <= y2) { add1(node, 1); return; } pushdown(node); int m = l + (r - l) / 2; if (m >= y1) change(node * 2, l, m, y1, y2); if (m+1 <= y2) change(node * 2 + 1, m + 1, r, y1, y2); v[node] = min(v[node*2], v[node*2+1]); } double query(int node, int l, int r, int y1, int y2) { if (y1 > r || y2 < l) return 100000000; if (r <= y2 && l >= y1) { return v[node]; } pushdown(node); int m = l + (r - l) / 2; return min(query(node * 2, l, m, y1, y2), query(node * 2 + 1, m + 1, r, y1, y2)); } int app[Max_N]; int main() { int T; cin >> T; while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); double l = 0; double r = 1; int flag = 0; while (true) { double mid = l + (r - l) / 2; build(1, 1, n, mid); flag = 0; memset(app, 0, sizeof(app)); //cout << mid << endl; for (int i = 1; i <= n; i++) { change(1, 1, n, app[a[i]] + 1, i); min1 = query(1, 1, n, 1, i); if (min1 <= mid * (i*1.0 + 1)) { flag = 1; break; } app[a[i]] = i; } if (flag) r = mid; else l = mid; if (r - l <= 0.000001) break; } printf("%.10lf\n", (l + r) / 2); } return 0; }