HDU-6070 Dirt Ratio-线段树+分数规划

题意：
给你一个数组，找一段区间使得区间内不同数的个数与区间长度的比值最小。

Solution：
这是一道经典的分数规划题，考虑二分答案k，那么我们的目标就是找一段区间使得val/len<=k，val是区间内不同的数的个数，len是区间长度，转化一下可以得到val-k*len<=0，我们可以利用线段树达到快速查询的效果：维护区间最小值，pre[a[i]]记录上一个值为a[i]的数出现的位置，每次把[pre[i]+1,i]这段区间+1，[1,i]这段区间-k，每次操作完后求[1,i]区间的最小值，如果小于0那么说明符合条件。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=60010;
struct tree{
	int l,r;
	double v,tag;
}tr[4*N];
int n,T,a[N];
int pre[N];
const double eps=1e-6;
void update(int i)
{
	tr[i].v=min(tr[i<<1].v,tr[i<<1|1].v);
} 
void build(int i,int l,int r)
{
	tr[i].l=l;tr[i].r=r;tr[i].v=0;tr[i].tag=0;
	if (l==r) return;
	int mid=l+r>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
}
void add(int i,double x)
{
	tr[i].tag+=x;
	tr[i].v+=x;
}
void pushdown(int i)
{
	if (tr[i].tag)
	{
		if (tr[i].l==tr[i].r) {tr[i].tag=0;return;} 
		add(i<<1,tr[i].tag);
		add(i<<1|1,tr[i].tag);
		tr[i].tag=0;
	} 
}
void modify(int i,int l,int r,double v)
{
	int L=tr[i].l,R=tr[i].r;
	if (L>r||l>R) return;
	if (l<=L&&R<=r) {add(i,v);return;}
	pushdown(i);
	modify(i<<1,l,r,v);
	modify(i<<1|1,l,r,v);
	update(i);
}
double query(int i,int l,int r)
{
	int L=tr[i].l,R=tr[i].r;
	if (L>r||l>R) return 1e9;
	if (l<=L&&R<=r) return tr[i].v;
	pushdown(i);
	double ans=1e9;
	ans=min(ans,query(i<<1,l,r));
	ans=min(ans,query(i<<1|1,l,r));
	return ans;
}
bool solve(double k)
{
	build(1,1,n);
	memset(pre,0,sizeof(pre));
	for (int i=1;i<=n;i++)
	{
		modify(1,pre[a[i]]+1,i,1);
		modify(1,1,i,-k);
		if (query(1,1,i)<=0) return 1;
		pre[a[i]]=i;
	}
	return 0;
}
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		double l=0,r=1,ans=1;
		while (r-l>=eps)
		{
			double mid=(l+r)/2;
			if (solve(mid)) ans=mid,r=mid;
			else l=mid;
		}
		printf("%.5f\n",ans);
	}
}