題目連結
題意:
給定一個數列 a 長度為 n (n <= 6e5, a1, a2, ..., an <= n),求其子串中 出現的不同數字個數 與 子串的長度 之比的最小值。
這道題的特殊之處在于其是special judge
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 .
如果有什麼正經(霧)的做法,那麼這個值應該是個定值啊,不至于會............
故:二分!
二分後怎麼check呢...賽後看題解(。
題解如是說:
二分答案midmid,檢驗是否存在一個區間滿足\frac{size(l,r)}{r-l+1}\leq midr−l+1size(l,r)≤mid,也就是size(l,r)+mid\times l\leq mid\times (r+1)size(l,r)+mid×l≤mid×(r+1)。
從左往右枚舉每個位置作為rr,當rr變化為r+1r+1時,對sizesize的影響是一段區間加11,線段樹維護區間最小值即可。
再說明白一點,當處理到第 i 個數時,線段樹中中每個節點的值的含義為:
1. 每個葉子節點 [L, L] 的值為 [L, i] 一段的 val,
2. 每個非葉子結點 [L, R] 的值為 min{ [l, i].val | L <= l <= R }.
想明白這一點就好寫了
Code:
#include <bits/stdc++.h>
#define maxn 60010
#define inf 0x3f3f3f3f
#define eps 1e-5
#define lson (rt << 1)
#define rson (rt << 1 | 1)
struct tree {
int l, r, tag;
double val;
}tr[maxn * 4];
double v;
int n, pre[maxn], pos[maxn];
inline int midi(int a, int b) { return a + b >> 1; }
inline double min(double a, double b) { return a < b ? a : b; }
void build(int rt, int l, int r, double x) {
tr[rt].l = l; tr[rt].r = r; tr[rt].val = x * l; tr[rt].tag = 0;
if (l == r) return;
int mid = midi(l, r);
build(lson, l, mid, x); build(rson, mid + 1, r, x);
}
inline void push_up(int rt) {
tr[rt].val = min(tr[lson].val, tr[rson].val);
}
inline void push_down(int rt) {
if (tr[rt].tag) {
tr[lson].tag += tr[rt].tag; tr[lson].val += tr[rt].tag;
tr[rson].tag += tr[rt].tag; tr[rson].val += tr[rt].tag;
tr[rt].tag = 0;
}
}
void modify(int rt, int l, int r, int r0) {
if (tr[rt].l == l && tr[rt].r == r) {
tr[rt].tag += 1;
tr[rt].val += 1;
return;
}
push_down(rt);
int mid = midi(tr[rt].l, tr[rt].r);
if (r <= mid) modify(lson, l, r, r0);
else if (l > mid) modify(rson, l, r, r0);
else { modify(lson, l, mid, r0); modify(rson, mid + 1, r, r0); }
push_up(rt);
}
void query(int rt, int r) {
if (tr[rt].r <= r) { v = min(v, tr[rt].val); return; }
if (tr[rt].l == tr[rt].r) return;
push_down(rt);
int mid = midi(tr[rt].l, tr[rt].r);
query(lson, r);
if (r > mid) query(rson, r);
push_up(rt);
}
bool check(double x) {
// printf("x : %.3f\n", x);
build(1, 1, n, x);
for (int r = 1; r <= n; ++r) {
modify(1, pre[r] + 1, r, r);
v = inf;
query(1, r);
if (v <= (r + 1) * x) {
// printf("%d\n", r);
return true;
}
}
return false;
}
void work() {
memset(pos, 0, sizeof(pos));
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
pre[i] = pos[x];
pos[x] = i;
}
double l = 0, r = 1.0, mid;
while (r - l > eps) {
mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
printf("%.10f\n", mid);
}
int main() {
int T;
scanf("%d", &T);
while (T--) work();
return 0;
}