转化限制+分析变量变化引起的答案变化：Gym - 104065D

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133844333

https://vjudge.net/contest/587311#problem/H

先转化一波条件：

  • pi≥1Xp_i\ge \frac 1 X

  • pi≤11−Yp_i\le \frac 1 {1-Y}

所以我们按 pp 排序， sumxsum_x 必然是后缀， sumysum_y 必然是前缀。

同时发现在 XX 变大， sumxsum_x 必然变大。 YY 同理。

观察式子：
在这里插入图片描述

假设 sumysum_y 定，且 maxy∗Y≥sumx∗Xmax_y*Y\ge sum_x*X ，则显然在满足条件下 XX 越大越好。

然后就可以two-pointers了。

要去重，不然过不了 脑抽出题人卡精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define M
//#define mo
#define N 1000010
struct node {
	double p, c; 
}a[N];
int n, m, i, j, k, T;
double ans, S1[N], S2[N]; 
double x, y; 
int l, r; 

double calc_X(double p) {
	if(p==0) return -1; 
	return 1.0/p; 
}

double calc_Y(double p) {
	if(p==1) return -1; 
	return 1.0/(1-p); 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); 
	for(i=1; i<=n; ++i) scanf("%lf%lf", &a[i].p, &a[i].c); 
	sort(a+1, a+n+1, [] (node x, node y) { return x.p < y.p; }); 
	a[n+1].p=1; 
	for(i=1, j=0; i<=n+1; ++i) {
		if(a[i].p!=a[j].p) a[++j]=a[i]; 
		else a[j].c+=a[i].c; 
	} 
	n=j; 
	S1[0]=a[0].c; 
	for(i=1; i<=n; ++i) S1[i]=S1[i-1]+a[i].c; 
	for(i=n; i>=0; --i) S2[i]=S2[i+1]+a[i].c; 
//	for(i=0; i<=n; ++i) printf("%lf %lf\n", a[i].p, a[i].c); 
//	for(i=0; i<=n; ++i) printf("%lf ", S1[i]); printf("\n"); 
//	for(i=0; i<=n; ++i) printf("%lf ", S2[i]); printf("\n"); 
	for(l=0, r=n; l<=n; ++l) {
		y=calc_Y(a[l].p); if(y<0) break; 
		while(calc_X(a[r-1].p)>=0 && S2[r-1]*calc_X(a[r-1].p)<=S1[l]*y) --r; 
		for(i=min(n, r+10); i>=max(1ll, r-10); --i) {
			x=calc_X(a[i].p); if(x<0) continue; 
			if(i<=l) continue; 
//			printf("%lld %lld (%lf %lf)[%lf %lf] %lf\n", l, i, y, x, S1[l], S2[i], max(S1[l]*y, S2[i]*x)); 
			ans=max(ans, S1[l]+S2[i]-max(S1[l]*y, S2[i]*x)); 
		}
	}
	printf("%.11lf", ans); 
	return 0;
}