HDU 6070 Partition
Problem :
给一段长度为n的序列，要求找出一段区间，使得这段区间的数字种类除以区间长度最小。输出最后的答案即可。(n <= 60000)(9s时限)
Solution :
显然，答案是0~1中的一个数字，可以很自然的想到二分答案的做法。假设目前二分到的答案为mid，那么需要判断
\[\frac{cnt(l, r)}{r- l + 1} <= mid
\]
\]
其中cnt(l,r)为l到r这个区间内的数字种类。变化一下式子可以得到:
\[cnt(l, r) + mid * l <= mid * (r + 1)
\]
\]
通过枚举有端点r，使用线段树维护左边的式子，每当右端点r向右移动1时，所影响的区间为r到对应颜色上一次出现的位置，区间整体加1就行了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define eps 1e-10
const int N = 1e5 + 8;
int a[N], pre[N];
int n;
struct Segment_Tree
{
double tag[N << 2];
double lazy[N << 2];
void pushup(int rt)
{
int l = rt << 1, r = rt << 1 | 1;
tag[rt] = min(tag[l], tag[r]);
}
void pushdown(int rt)
{
int l = rt << 1, r = rt << 1 | 1;
if (lazy[rt])
{
tag[l] += lazy[rt];
tag[r] += lazy[rt];
lazy[l] += lazy[rt];
lazy[r] += lazy[rt];
lazy[rt] = 0;
}
}
void build(int l, int r, int rt, double x)
{
tag[rt] = lazy[rt] = 0;
if (l == r)
{
tag[rt] = l * x;
return;
}
int m = l + r >> 1;
build(l, m, rt << 1, x);
build(m + 1, r, rt << 1 | 1, x);
pushup(rt);
}
void update(int L, int R, int val, int l, int r, int rt)
{
if (L <= l && r <= R)
{
tag[rt] = tag[rt] + val;
lazy[rt] += val;
return;
}
pushdown(rt);
int m = l + r >> 1;
if (L <= m) update(L, R, val, l, m, rt << 1);
if (m < R) update(L, R, val, m + 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 tag[rt];
}
pushdown(rt);
int m = l + r >> 1;
double ans = 1e12;
if (L <= m) ans = min(ans, query(L, R, l, m, rt << 1));
if (m < R) ans = min(ans, query(L, R, m + 1, r, rt << 1 | 1));
return ans;
}
}T;
void init()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
}
int sgn(double x)
{
if (fabs(x) < eps) return 0;
if (x > 0) return 1;
return -1;
}
bool check(double mid)
{
for (int i = 1; i <= n; ++i) pre[i] = 0;
T.build(1, n, 1, mid);
for (int i = 1; i <= n; ++i)
{
T.update(pre[a[i]] + 1, i, 1, 1, n, 1);
pre[a[i]] = i;
if (sgn(mid * (i + 1) - T.query(1, i, 1, n, 1) >= 0)) return 1;
}
return 0;
}
void solve()
{
double l = 0, r = 1;
while (l + eps < r)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid; else l = mid;
}
printf("%.6f\n", l);
}
int main()
{
cin.sync_with_stdio(0);
int T; cin >> T;
for (int cas = 1; cas <= T; ++cas)
{
init();
solve();
}
}