原题链接

题目链接

思路

邻项交换模板题。

考虑两个相邻项，不妨记为以及，证明如果，那么交换这两项可以使得危险度最大值更小。

证明：

不妨记。交换之前，第项对应的危险度为，第项的危险度为，局部的最大危险度为；交换 之后，第项对应的危险度为，第项对应的危险度为，局部的最大值为。由于，可知，故而当时， 有交换之前的最大危险度大于交换之后的最大危险度。

由此，以进行排序，排序之后序列中的最大危险度最小。

实现

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
struct node {
    ll w;
    ll s;
};

bool cmp(const node & n1, const node &n2){
    return (n1.w+n1.s)>(n2.w+n2.s);
}

const int N = 50000 + 10;
node a[N];

int main(){
    int n ;
    cin >> n;
    ll sum =0;
    for(int i=0;i<n;i++){
        cin>>a[i].w>>a[i].s;
        sum += a[i].w;
    }
    
    sort(a, a+n, cmp);
    ll ans = -999999999;
    for(int i=0;i<n;i++){
        ans = max(sum-a[i].w-a[i].s, ans);
        sum -= a[i].w;
    }
    cout<<ans<<endl;
    return 0;
}c