HDU-6070 Dirt Ratio(二分+线段树+分数规划)
(有任何问题欢迎留言或私聊 && 欢迎交流讨论哦
目录
题意:传送门
原题目描述在最下面。
求\(sum/len\)最小值。\(sum\)是一段区间内不同数字的个数,\(len\)是这段区间的长度。
思路:
首先预处理出每个数上一次出现的位置\(pre[i]\)和最后一次出现的位置\(lst[i]\)。这个操作在静态求区间内不同数的个数和动态求区间内不同数的个数都有用到。
法一:
二分答案\(mid\)。枚举序列,每加入一个数就在\(pre[i]-i\)区间加一,因为在以\(i\)为右端点的所有区间内,这么区间多了一个新数字。
对于\(sum/len\leq mid\; \rightarrow sum - len * mid \leq 0\)。我们已经处理了\(sum\),对于\(len*mid\),就在解决每次插入一个数后,在\(1-i\)区间减去\(k\)。最后查询区间最小值,如果小于\(0\)则此\(mid\)符合还可以更小。
因为我们每加入一个数后,查询的是以\(i\)为右端点的区间最小值,所以很自然的就要\(1-i\)每次减去\(k\)。这样才符合上述表达式。感觉画个图更好理解。
法二:
化简表达式为:$sum(L,R)+Lmid \leq Rmid $
\(sum\)的更新和上面一样,但是左边多了一项\(l*mid\)。
怎么办呢?解决方法就是在线段树的每个端点处的值初始化为\(l*mid\)(\(l\)是到\(1\)的距离)。
然后每此更新完后查询区间最小值\(mmin\),如果\(mmin\leq i*mid\)则此\(mid\)符合还可以更小
AC代码:
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
const int N = 1e5+7;
int n;
int lst[N],pre[N],ar[N];
double sum[N<<2],lazy[N<<2];
void push_up(int rt){
sum[rt]=min(sum[lson],sum[rson]);
}
void push_down(int rt){
if(lazy[rt]){
lazy[lson]+=lazy[rt];
lazy[rson]+=lazy[rt];
sum[lson]+=lazy[rt];
sum[rson]+=lazy[rt];
lazy[rt]=0;
}
}
void update(int L,int R,int l,int r,double c,int rt){
if(L<=l&&r<=R){
sum[rt] += c;
lazy[rt] += c;
return;
}
push_down(rt);
int mid = (l+r)>>1;
if(L<=mid) update(L,R,l,mid,c,lson);
if(R>mid) update(L,R,mid+1,r,c,rson);
push_up(rt);
}
double query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return sum[rt];
}
push_down(rt);
int mid = (l+r)>>1;
double sum=n;
if(L<=mid) sum = min(sum, query(L,R,l,mid,lson));
if(R>mid) sum = min(sum, query(L,R,mid+1,r,rson));
push_up(rt);
return sum;
}
/*
1
5
1 2 1 2 3
sum/len最小值
sum/len <= mid
sum - len*mid <= 0
sum 区间不同数字的个数
len 区间长度
*/
bool ok(double e){
mme(sum,0);mme(lazy,0);
for(int i=1;i<=n;++i){
update(pre[i]+1,i,1,n,1,1);
update(1,i,1,n,-e,1);
if(query(1,i,1,n,1)<=0)return 1;
}
return false;
}
int main(){
int tim;
scanf("%d",&tim);
while(tim--){
scanf("%d",&n);
mme(lst,0);mme(pre,0);
for(int i=1;i<=n;++i){
scanf("%d",&ar[i]);
pre[i]=lst[ar[i]];
lst[ar[i]]=i;
}
double l=0,r=1,mid;
for(int i=0;i<20;++i){
mid=(l+r)/2;
if(ok(mid))r=mid;
else l=mid;
}
printf("%.5f\n", r);
}
return 0;
}
####原题目描述:
![这里写图片描述](https://img-blog.csdn.net/20180808090410937?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTk5MDY3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)
最新文章
- IOS开发之代码之九宫格
- 【Nginx】使用Nginx做反向代理时,关于被代理服务器相应的超时设置
- HTTP请求状态类
- 在Linux上安装JDK7
- SOAP Services for Python
- AWS s3 python sdk code examples
- 【自学php】第三天 - 读写文件
- 浅谈 IE下innerHTML导致的问题
- Kraken.js!
- 线上问题debug过程(cat,grep,tr,awk,sort,uniq,comm等工具的综合使用)
- Struts2的核心运行流程,原理图解
- 学习PID
- [Codeforces 946F]Fibonacci String Subsequences
- (网页)bootstrap模态框手动关闭(转)
- 转://Oracle 事务探索与实例(一)
- Handler实现线程间的通信2
- SDN交换机迁移2
- Android 之 Fagment 完全解析
- cannot send list of active checks to [ZabbixServerIp]: host [Zabbix server] not found
- VS2010/MFC编程入门之三十八(状态栏的使用详解)