「较小值最大」赌注

发表于 | 分类于

题目链接

ps：这道题是在校内模拟赛见到的，所以题目当然是模改过的啦=。= 原题提交链接在上面=。=

问题描述
一天，你进入了神仙 lzc的神仙赌场。 神仙 lzc 实在是肽聚了，他觉得用一个本体来虐人太无聊了，于是就造出了 N 个分身。 这 N 个分身每个都是庄家。 你可以到庄家那边下注，每次可以猜大猜小，猜一次一元钱。 每一次开彩前，你都可以到任意个庄家那里下赌注。 如果开彩结果是大，你就可以得到你之前猜大的庄家相应的 ai 元钱。 如果开彩结果是小，你就可以得到你之前猜小的庄家相应的 bi 元钱。 你可以在同一个庄家那里既猜大又猜小（这样是两块钱），也可以什么都不猜（这样不用 钱）。 现在你对这个整天装逼装弱的神仙 lzc 看得实在是不爽，想要从它的分身中坑走尽量多的 钱。 但是阴险狡诈爱装逼爱装弱的神仙 lzc 会根据你下注的信息控制开彩的结果，让你赢的钱 数尽量少。 问怎么样下注，才能坑走神仙 lzc 最多的钱。

输入
第一行一个数字 N。表示有 N 个庄家。 接下来 N 行，每行 2 个实数，分别表示这个庄家的 ai 和 bi。

输出
一个四位小数，表示最多能坑走神仙 lzc 的钱。

输入输出样例
输入样例

4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5

输出样例

0.5000

约定和数据范围
对于 20% 的数据，1 ≤ n ≤ 10；
对于 60% 的数据，1 ≤ n ≤ 1000；
对于 100% 的数据，1 ≤ n ≤ 100000， 1.0 ≤ ai,bi ≤ 1000.0。

看完题目之后首先我就被样例给搞晕啦，0.5000是怎么来的，嗯……是这样来的：

样例解释

最优策略是第一个庄家压小和第三个庄家压大和第四个庄家压大：

如果本局开小，收益是 3.7-3=0.7。
如果本局开大，收益是 1.6+1.9-3=0.5。
最小可能收益是 0.5。

原来是这样！我们可以进行任意的押注选择，神仙lzc会根据你的选择，让你能赚到的钱尽量少，就是说如果你在这局游戏中压了一些大，压了一些小，开奖的时候神仙lzc会根据开奖后你能够赚到的钱数进行阴险操纵，如果开大你能赚到的钱更多，那么他就会操纵开小，如果开小你能赚到的钱更多，那么他就操纵开大。

我们既可以压大又可以压小，可以同时压，可以同时不压，那么压大和压小之间就是完全独立的选择，互不影响。
我们的成本为压大的个数+压小的个数（压一次一元）， 收益为压大收益和压小收益中较小的一个 - 成本（有可能为负，例如第一个庄家既压大又压小，lzc操纵开大， 那么收益为：1.4 - 2（押注两次的成本） = -0.6，这样我们就赔了0.6元）。

所以我们的工作即为使得 （开奖收益较小值 - 成本）最大。

既然成本都为一元， 那么同等情况下压受益较大的赚钱肯定更多。a[]与b[]之间互不影响，所以我们将a[] 及b[]从大到小进行排序, 然后在原数组上求出前缀和（a[i]即为压i个大，b[i]即为压i个小）。 然后从小到大枚举我们压i个大及压j个小能获得的最终收益，取max即为答案！

附上代码：

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
#include <cstdio>
#include <iostream>
#include <cctype>
#include <algorithm>
#define DEBUG(x) std::cerr << #x << " = " << x << std::endl
#define minxy(x, y) ((x) < (y) ? (x) : (y))
#define maxxy(x, y) ((x) > (y) ? (x) : (y))
inline int read() {
	char ch = getchar(); int res = 0; int flag = 1;
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') flag = -1;
	for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + ch - '0';
	return (res * flag);
}
const int N_MAX = 100007;
int n;
double ans, a[N_MAX], b[N_MAX], har;
bool cmp(double r1, double r2) {
	return r1 > r2;
}//sort的比较函数
int main() {
    freopen("coin.in", "r", stdin);
    freopen("coin.out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; i++) {
		scanf("%lf%lf", &a[i], &b[i]);
	}
	std::sort(a + 1, a + n + 1, cmp);
	std::sort(b + 1, b + n + 1, cmp);
    //排序
    for(int i = 2; i <= n; i++) b[i] += b[i - 1];
    for(int i = 2; i <= n; i++) a[i] += a[i - 1];
    //求前缀和
    for(int i = 1; i <= n; i++){
       for(int j = 1; j <= n; j++) {
            har = minxy(a[i], b[j]) - i - j;
            //minxy(a[i], b[i]) : lzc会操纵我们得到的是收益较小的一个
            //- i - j ： 减去我们压了(i + j)个的成本
            ans = maxxy(ans, har);
            //求最终收益的最大值
       }
    }
    //枚举所有方案
    printf("%.4lf",ans);
	fclose(stdin);
    fclose(stdout);
	return 0;
}

很开心地我们就提交了程序， 哭着回来了。60分。
n^2的复杂度TLE了 QAQ

这样想，既然较大收益已经固定的时候，我们把较大收益定住，然后使较小收益尽量大，较小收益越大，最终收益也就越大！
这样只需要跑一遍定压大的情况，再跑一遍定压小的情况，求下最终收益max就可以了。复杂度就从O(n^2)优化到O(4n)了，轻松跑过~

附上代码!：

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
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 100005;
int n;
double ans, a[MAXN] , b[MAXN];
inline bool cmp(double x , double y) {
	return x > y;
}
int main() {
	scanf("%d" ,&n);
	for(int i = 1 ; i <= n ; i++) 
		scanf("%lf%lf" ,a + i , b + i);
	sort(a + 1 , a + n + 1 , cmp);
	sort(b + 1 , b + n + 1 , cmp);
    //单次押注收益排序
    
	for(int i = 1 ; i <= n ; i++) {
		a[i] += a[i - 1];
		b[i] += b[i - 1];
	}//前缀和
	for(int i = 1 , j = 1 ; i <= n ; i++) {
		while(j <= n && b[j] < a[i]) j++;
		if(j <= n) ans = max(ans , a[i] - i - j );
	}
    //定压大，移压小
    
	for(int i = 1 , j = 1 ; i <= n ; i++) {
		while(j <= n && a[j] < b[i]) j++;
		if(j <= n) ans = max(ans , b[i] - i - j );
	}
    //定压小，移压大
	printf("%.4lf\n",ans );
	return 0;
}