题目描述
现在有 n 个A类灯泡和 n 个B类灯泡，每个灯泡都有各自的权值。
我们将这些灯泡分为 n 组，每组包含一个来自A类的灯泡和一个来自B类的灯泡。
你可以从中选取任意个灯泡，每选取一个灯泡需要花费 1 的代价。
在你选取完之后，系统会随机在A类和B类中选择一个类型，并点亮那一类的所有灯泡。你选取的每个点亮的灯泡会给你带来等于它权值的收益。
现在请你合理选取灯泡，以最大化可能的最小收益。你只需要求出来这个收益即可。
输入格式
第一行一个正整数 n ，表示灯泡的组数。
接下来 n 行每行两个空格隔开的实数 Ai,Bi。分别表示属于这组的A灯泡和B灯泡的权值。输入的实数不会超过四位小数。
输出格式
输出最大化的最小可能收益，请输出到小数点后恰好四位。
输入输出样例 #1
输入 #1
4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5
输出 #1
0.5000
说明/提示
样例解释
最优策略是选择第一组的B灯泡和第三组的A灯泡和第四组的A灯泡：
- 如果B类灯泡被点亮，收益是 3.7−3=0.7。
- 如果A类灯泡被点亮，收益是 1.6+1.9−3=0.5。
最小可能收益是 0.5。
数据范围
对于所有测试点，有 1.0≤Ai,Bi≤1000.0，0≤n≤105。
代码参考
#include<bits/stdc++.h>
using namespace std;int n;
double ans;
double A[100001], B[100001];
bool t[100001][2]; bool cmp(double a, double b)
{return a > b;
}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);double a = 0.0, b = 0.0;for(double i = 1, j = 1; i <= n && j <= n;) {int x = i, y = j; a += A[x] * double(!t[x][0]);b += B[y] * double(!t[y][1]);t[x][0] = t[y][1] = 1; // 标记已遍历的数据 ans = max(ans, min(a - i - j, b - i - j)); // 计算价值 if(a >= b) j++;if(a <= b) i++;}printf("%.4lf\n", ans); // 输出保留4位小数return 0;
}