HDU 6070 Dirt Ratio （线段树+二分）

Description

Input

The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.In each test case, there is an integer n(1≤n≤60000) in the first line, denoting the length of the submission list.In the next line, there are n positive integers a1,a2,…,an(1≤ai≤n), denoting the problem ID of each submission.

Output

For each test case, print a single line containing a floating number, denoting the lowest ”Dirt Ratio”. The answer must be printed with an absolute error not greater than 10^−4.

Sample Input

151 2 1 2 3

Sample Output

0.5000000000

题意

有一个长度为 n 的序列，求所有区间 [l,r]

思路

二分答案 mid ，检验是否存在一个区间满足 size(l,r)r−l+1<=mid

即 size(l,r)+mid×l<=mid×(r+1)

线段树保存 size(l,r)+mid×l ，然后我们可以枚举右端点 r ，而在右端点加入时带来了自己的一份颜色，标记它上一次的出现位置，则 r

AC 代码

#include #include #include #include using namespace std;typedef __int64 LL;const double eps = 1e-6;const int maxn = 61000;#define inf 0x3f3f3fint last_appear[maxn];int a[maxn],n;double val[maxn << 2], laz[maxn << 2];void pushUp(int rt){ val[rt] = min(val[rt << 1], val[rt << 1 | 1]);}void pushDown(int rt){ val[rt << 1] += laz[rt]; laz[rt << 1] += laz[rt]; val[rt << 1 | 1] += laz[rt]; laz[rt << 1 | 1] += laz[rt]; laz[rt] = 0;}void build(int l, int r, int rt, double v){ laz[rt] = 0; if (l == r) { val[rt] = v * l; return; } int mid = (l + r) >> 1; build(l, mid, rt << 1, v); build(mid + 1, r, rt << 1 | 1, v); pushUp(rt);}void update(int L, int R, int v, int l, int r, int rt){ if (L <= l && r <= R) { val[rt] += v; laz[rt] += v; return; } if (laz[rt] != 0) pushDown(rt); int mid = (l + r) >> 1; if (L <= mid) update(L, R, v, l, mid, rt << 1); if (mid < R) update(L, R, v, mid + 1, r, rt << 1 | 1); pushUp(rt);}double query(int L, int R, int l, int r, int rt){ if (L <= l && r <= R) return val[rt]; if (laz[rt] != 0) pushDown(rt); int mid = (l + r) >> 1; double ret = inf; if (L <= mid) ret = query(L, R, l, mid, rt << 1); if (mid < R) ret = min(ret, query(L, R, mid + 1, r, rt << 1 | 1)); return ret;}bool judge(double mid){ build(1, n, 1, mid); memset(last_appear, 0, sizeof(last_appear)); // 该数字上一次的出现位置 for (int i = 1; i <= n; i++) { update(last_appear[a[i]] + 1, i, 1, 1, n, 1); last_appear[a[i]] = i; if (query(1, i, 1, n, 1) < mid * (i + 1)) return true; } return false;}int main(){ int T; cin >> T; while (T--) { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; double low = 0, high = 1, ans; while (high - low > eps) // 二分答案 { double mid = (low + high) / 2.0; if (judge(mid)) high = (ans = mid) - eps; else low = mid + eps; } printf("%.9lf\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。