HDU 6070 二分+线段树 Dirt Ratio

Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 335 Accepted Submission(s): 105
Special Judge

Problem Description

In ACM/ICPC contest, the ''Dirt Ratio'' of a team is calculated in the following way. First let's ignore all the problems the team didn't pass, assume the team passed

. If the ''Dirt Ratio'' of a team is too low, the team tends to cause more penalty, which is not a good performance.

HDU 6070 二分+线段树
Dirt Ratio

Picture from MyICPC

Input

The first line of the input contains an integer

, denoting the problem ID of each submission.

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

Sample Input

1 2 1 2 3

Sample Output

0.5000000000

Hint

For every problem, you can assume its final submission is accepted.

Source

2017 Multi-University Training Contest - Team 4

题意：给你一个长度为n的区间 X=区间不同数的个数 Y=区间长度求子区间X/Y的最小值

题解：二分答案mid check X/Y<=mid

X/Y=X/(r-L+1)<=mid

=> X+L*mid<=(r+1)*mid

建树初始每个点的maxn为L*mid

从左向右遍历右边界遍历到r 更新(last[r]+1,r) 值增加1 last[r]表示a[r]相同值的上一个位置

r之前的每个结点L存的是L到r不同数的个数X+L*mid (这些便是不等式的左边）取最小值与 (r+1)*mid 比较

  1 #pragma comment(linker, "/STACK:102400000,102400000")
  2 #include <bits/stdc++.h>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <iostream>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <algorithm>
  9 #include <cmath>
 10 #include <cctype>
 11 #include <map>
 12 #include <set>
 13 #include <queue>
 14 #include <bitset>
 15 #include <string>
 16 #include <complex>
 17 #define LL long long
 18 #define mod 1000000007
 19 using namespace std;
 20 int t;
 21 int n;
 22 int a[65003];
 23 int last[65003];
 24 map<int,int> mp;
 25 struct node
 26 {
 27     int l,r;
 28     double maxn;
 29     int add;
 30 } tree[500005];
 31 void buildtree(int root ,int left,int right,double zz)
 32 {
 33     tree[root].l=left;
 34     tree[root].r=right;
 35     tree[root].add=0;
 36     if(left==right)
 37     {
 38         tree[root].maxn=left*zz;
 39         return ;
 40     }
 41     int mid=(left+right)>>1;
 42     buildtree(root<<1,left,mid,zz);
 43     buildtree(root<<1|1,mid+1,right,zz);
 44     tree[root].maxn=min(tree[root<<1].maxn,tree[root<<1|1].maxn);
 45 }
 46 void pushdown(int root)
 47 {
 48     if(tree[root].add==0) return ;
 49     tree[root<<1].add+=tree[root].add;
 50     tree[root<<1|1].add+=tree[root].add;
 51     tree[root<<1].maxn+=tree[root].add;
 52     tree[root<<1|1].maxn+=tree[root].add;
 53     tree[root].add=0;
 54 }
 55 void update(int root,int left,int right,int c)
 56 {
 57     if(tree[root].l==left&&tree[root].r==right)
 58     {
 59         tree[root].add+=c;
 60         tree[root].maxn+=c;
 61         return ;
 62     }
 63     pushdown(root);
 64     int mid=(tree[root].l+tree[root].r)>>1;
 65     if(right<=mid)
 66     {
 67         update(root<<1,left,right,c);
 68     }
 69     else
 70     {
 71         if(left>mid)
 72             update(root<<1|1,left,right,c);
 73         else
 74         {
 75             update(root<<1,left,mid,c);
 76             update(root<<1|1,mid+1,right,c);
 77 
 78         }
 79     }
 80     tree[root].maxn=min(tree[root<<1].maxn,tree[root<<1|1].maxn);
 81 }
 82 double query(int root,int left,int right)
 83 {
 84     if(left>right)
 85         return 0;
 86     if(tree[root].l==left&&tree[root].r==right)
 87     {
 88         return  tree[root].maxn;
 89     }
 90     pushdown(root);
 91     int mid=(tree[root].l+tree[root].r)>>1;
 92     if(right<=mid)
 93         return query(root<<1,left,right);
 94     else
 95     {
 96         if(left>mid)
 97             return query(root<<1|1,left,right);
 98         else
 99             return  min(query(root<<1,left,mid),query(root<<1|1,mid+1,right));
100     }
101 }
102 bool check (double x)
103 {
104     buildtree(1,1,n,x);
105     for(int i=1; i<=n; i++)
106     {
107         update(1,last[i]+1,i,1);
108         double zha=(double)query(1,1,i);
109         if(zha<=(i+1)*x)
110             return true;
111     }
112     return false;
113 }
114 int main()
115 {
116     scanf("%d",&t);
117     for(int kk=1;kk<=t;kk++){
118     scanf("%d",&n);
119     mp.clear();
120     for(int i=1; i<=n; i++){
121         scanf("%d",&a[i]);
122         last[i]=mp[a[i]];
123         mp[a[i]]=i;
124     }
125     double l=0,r=1.0,mid,ans;
126     while(abs(l-r)>=0.00001)
127     {
128         mid=(l+r)/2;
129         if(check(mid)){
130             ans=mid;
131             r=mid;
132         }
133         else
134           l=mid;
135     }
136     printf("%f
",ans);
137  }
138     return 0;
139 }

HDU 6070 二分+线段树 Dirt Ratio

相关推荐