【wqs二分套wqs二分】HHHOJ#15. 赤

这个wqs二分并不熟练……

题目描述

题目分析

两维都用wqs二分，其他没有什么特殊之处。

重点在于，wqs二分还原最优解的时候，增量是强制给的k。

 1 #include<bits/stdc++.h>
 2 const int maxn = 100035;
 3 const double eps = 1e-9;
 4 
 5 int n,a,b,usa,usb;
 6 double bet,ans,coa,cob,p[maxn],q[maxn];
 7 
 8 bool match()
 9 {
10     double k1=coa,k2=cob;
11     usa = usb = 0, ans = 0;
12     for (int i=1, opt=0; i<=n; i++)
13     {
14         double v = 0;opt=0;
15         if (p[i]-k1 > v) opt = 1, v = p[i]-k1;
16         if (q[i]-k2 > v) opt = 2, v = q[i]-k2;
17         if (p[i]+q[i]-p[i]*q[i]-k1-k2 > v)
18             opt = 3, v = p[i]+q[i]-p[i]*q[i]-k1-k2;
19         if (opt==1||opt==3) usa++;
20         if (opt==2||opt==3) usb++;
21         ans += v;
22     }
23     return usb <= b;
24 }
25 bool check()
26 {
27     double l = 0, r = 1.0, bet;
28     for (cob=(l+r)/2.0; r-l>eps; cob=(l+r)/2.0)
29         if (match()) bet = r = cob;
30         else l = cob;
31     cob = bet;
32     match();
33     return usa <= a;
34 }
35 int main()
36 {
37     while (scanf("%d%d%d",&n,&a,&b)!=EOF)
38     {
39         for (int i=1; i<=n; i++) scanf("%lf",&p[i]);
40         for (int i=1; i<=n; i++) scanf("%lf",&q[i]);
41         double l = 0, r = 1.0;
42         for (coa=(l+r)/2.0; r-l>eps; coa=(l+r)/2.0)
43             if (check()) bet = coa, r = coa;
44             else l = coa;
45         coa = bet;
46         check();
47         ans += 1.0*a*coa+1.0*b*cob;　　//这里补偿答案用a,b
48         printf("%.5lf
",ans);
49     }
50     return 0;
51 }

END