[传送门](P4653 [CEOI 2017] Sure Bet - 洛谷)
分析
-
显然在同一类中选取灯泡越大越好。
-
如果某一类中选取灯泡比另一类比另一类多太多，会造成较大的浪费（每次选灯泡收益-1）
-
于是直觉告诉我们，AB两类的灯泡选取应该尽量平均
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
double A[N], B[N];//记录每个灯泡收益
double a = 0.0000, b = 0.0000; //用于记录两种开灯方式对应的收益（）
bool choose[N][2];//记录灯泡是否被选择
double ans = -1e9;//更新答案bool cmp(double x, double y)
{return x > y;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;//特判if (n == 0){cout << "0.0000";return 0;}for (int i = 1; i <= n; i++)cin >> A[i] >> B[i];
//从大到小重排sort(A + 1, A + 1 + n, cmp);sort(B + 1, B + 1 + n, cmp);
//尽可能平均地选灯泡for (int i = 1, j = 1; i <= n && j <= n;){double x = i, y = j;a += A[i] * double(!choose[i][0]);b += B[j] * double(!choose[j][1]);//因为每个灯泡选取收益>=1，故A[1]与B[1]一定选取choose[j][1] = choose[i][0] = 1;ans = max(ans, min(a - x - y, b - x - y));if (a <= b)i++;if (b <= a)j++;}if (ans>0)//若ans为正printf("%.4lf", ans);else//若ans为负，那么一个灯泡也不选收益为0cout << "0.0000";return 0;
}