2017 Multi-University Training Contest - Team 4 HDU 6070 Dirt Ratio

---

题目链接：

HDU 6070

---

题目大意：

给你 n 个数， 让你选一个区间， 使得区间不同数的个数比区间长度尽可能的小。

数据范围：

1<=n<=60000,1<=ai<=n

---

解题思路:

这道题就是一道经典的找一个区间使得 ∑a∑b 尽可能的小。 首先我们会想到二分一个比值， 然后去check， check的点肯定是用线段树去维护。 我们把 size(l,r)r−l+1<=ratio 化简 根据官方题解我们把公式转化一下 size(l,r)+ratio∗l<=ratio∗(r+1) 在线段树里， 每次我们可以提前处理处每个位置也就是 mid∗l ， 之后枚举右区间， 每次移动， 左边第一个和他相同数到这个数区间的 size+1 ， 用线段树去更新， 再去查找一个最小值。

复杂度为 O(nlog2)

代码：

//2017-08-04 15:45 //2017-08-04 16:07 //2017-08-04 16:25 #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> using namespace std; typedef long long LL; const int MaxN = 6e4; const double INF = 1e9; double num[4 * MaxN + 5], add[4 * MaxN + 5]; int pre[MaxN + 5], last[MaxN + 5], a[MaxN + 5]; double vatal[MaxN + 5]; int T, n; void pushup(int rt){ num[rt] = min(num[rt << 1], num[rt << 1 | 1]);} void pushdown(int rt){ if(add[rt]){ add[rt << 1] += add[rt], add[rt << 1 | 1] += add[rt]; num[rt << 1] += add[rt], num[rt << 1 | 1] += add[rt]; add[rt] = 0; } } void build(int l, int r, int rt){ add[rt] = 0; if(l == r){ num[rt] = vatal[l]; return; } int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); pushup(rt); } void update(int L, int R, double x, int l, int r, int rt){ if(L > R) return; if(L <= l && R >= r){ add[rt] += x; num[rt] += x; return; } pushdown(rt); int mid = (l + r) >> 1; if(L <= mid) update(L, R, x, l, mid, rt << 1); if(R > mid) update(L, R, x, 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 num[rt]; pushdown(rt); int mid = (l + r) >> 1; double ret = INF; if(L <= mid) ret = min(ret, query(L, R, l, mid, rt << 1)); if(R > mid) ret = min(ret, query(L, R, mid + 1, r, rt << 1 | 1)); return ret; } bool check(double ratio){ for(int i = 1; i <= n; i++) vatal[i] = (i - 1) * ratio; build(1, n, 1); for(int i = 1; i <= n; i++){ update(pre[i] + 1, i, 1, 1, n, 1); double tmp = query(1, i, 1, n, 1); if(tmp <= ratio * i) return true; } return false; } double solve(){ double l = 0.0, r = 1.0, mid, ans = 1.0; for(int i = 0; i < 20; i++){ mid = (l + r) / 2; if(check(mid)) r = mid, ans = mid; else l = mid; } return ans; } int main(){ scanf("%d", &T); while(T--){ memset(last, 0, sizeof(last)); scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); pre[i] = last[a[i]]; last[a[i]] = i; } printf("%.10lf\n", solve()); } return 0; }