题目链接

Cow Acrobats POJ - 3045

思路

$$ 按w_i + s_i排序，贪心选取 $$

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 5e4 + 10;

long long a[MAXN], b[MAXN], id[MAXN];

bool cmp(int x, int y) {
    return a[x] + b[x] > a[y] + b[y];
}

int main() {
    int n;
    scanf("%d", &n);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &a[i], &b[i]);// don't forget &
        id[i] = i;
    }
    sort(id + 1, id + 1 + n, cmp);
    long long ans = -b[n];
    long long sum = 0;
    for (int i = n; i >= 1; i--) {
        int cur = id[i];
        ans = max(ans, sum - b[cur]);
        sum += a[cur];
    }
    printf("%lld", ans);
    return 0;
}