洛谷题单指南-常见优化技巧-P4653 [CEOI2017] Sure Bet

原题链接：https://www.luogu.com.cn/problem/P4653

题意解读：选中的灯泡中，某一类较少的总权值减去灯泡数量所得到的收益最大值。

解题思路：

注意，此题关键是：要使得较少的收益最大化

1、要最大化，意味着每次应该选择尽可能大权值的灯泡

2、要使A、B类中较少的收益最大化，意味着每次应该优先选择当前总权值较少的那一类灯泡的最大权值

如此贪心即可得到较少收益的最大值。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n;
double a[N], b[N], suma, sumb, ans;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    sort(a + 1, a + n + 1, greater<double>());
    sort(b + 1, b + n + 1, greater<double>());

    int i = 0, j = 0;
    while(i <= n && j <= n)
    {
        double s = min(suma, sumb) - i - j;
        ans = max(ans, s);

        if(suma > sumb) sumb += b[++j];
        else suma += a[++i];
    }
    printf("%.4f", ans);
}