#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010;

struct Cow {
    int w, s;
    bool operator< (const Cow& W)const {
        return w + s < W.w + W.s;
    }
} cows[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> cows[i].w >> cows[i].s;
    sort(cows, cows + n);

    int res = -2e9;
    for (int i = 0, s = 0; i < n; i++) {
        res = max(res, s - cows[i].s);
        s += cows[i].w;
    } 
    cout << res << endl;

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    int mid = a[n / 2], res = 0;
    for (int i = 0; i < n; i++) res += abs(a[i] - mid);
    cout << res << endl;

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    long long res = 0, s = 0;
    for (int i = 0; i < n - 1; i++) {
        s += a[i];
        res += s;
    }
    cout << res << endl;

    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

const int N = 10010;

int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    priority_queue<int, vector<int>, greater<int>> heap;
    int res = 0;
    for (int i = 0; i < n; i++) heap.push(a[i]);
    while (heap.size() > 1) {
        int x = heap.top(); heap.pop();
        int y = heap.top(); heap.pop();
        res += x + y;
        heap.push(x + y);
    }
    cout << res << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct Range {
    int l, r;
    bool operator< (const Range& W)const {
        return l < W.l;
    }
} range[N];

int main() {
    int st, ed;
    cin >> st >> ed;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;
    sort(range, range + n);

    int res = 0;
    bool flag = false;
    for (int i = 0; i < n; i++) {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st) {
            r = max(r, range[j].r);
            j++;
        }
        if (r < st) {
            flag = false;
            break;
        }
        res++;
        if (r >= ed) {
            flag = true;
            break;
        }
        i = j - 1;
        st = r;
    }
    if (!flag) cout << -1 << endl;
    else cout << res << endl;

    return 0;
}

按左端点排序

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct Range {
    int l, r;
    bool operator<(const Range& w)const {
        return l < w.l;
    }
} range[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;

    sort(range, range + n);
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i++) {
        if (heap.size() && range[i].l > heap.top()) {
            heap.pop();
            heap.push(range[i].r);
        } else heap.push(range[i].r);
    }
    cout << heap.size() << endl;

    return 0;
}

按右端点排序

将右端点从小到大排序后，倒过来看就和按左端点从小到大排序一样，不过此时大小关系跟左右端点是对称的。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct Range {
    int l, r;
    bool operator<(const Range& w)const {
        return r < w.r;
    }
} range[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;

    sort(range, range + n);
    priority_queue<int> heap;
    for (int i = n - 1; ~i; i--) {
        if (heap.size() && range[i].r < heap.top()) {
            heap.pop();
            heap.push(range[i].l);
        } else heap.push(range[i].l);
    }
    cout << heap.size() << endl;

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Range {
    int l, r;
    bool operator<(const Range& W)const {
        return r < W.r;
    }
} range[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;
    sort(range, range + n);

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i++) {
        if (range[i].l > ed) {
            res++;
            ed = range[i].r;
        }
    }
    cout << res << endl;

    return 0;
}

右端点排序

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Range {
    int a, b;
    bool operator<(const Range& r) const {
        return b < r.b;
    }
} ranges[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> ranges[i].a >> ranges[i].b;
    sort(ranges, ranges + n);

    int res = 0;
    int cur = -2e9;
    for (int i = 0; i < n; i++) {
        if (ranges[i].a > cur) {
            res++;
            cur = ranges[i].b;
        }
    }
    cout << res << endl;

    return 0;
}

左端点排序

若区间不相交则需要新增一个点，若相交则维护最小的右端点使得该点能覆盖所有已选区间。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Range {
    int l, r;
    bool operator<(const Range& range)const {
        return l < range.l;
    }
} range[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;

    sort(range, range + n);
    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i++) {
        if (range[i].l > ed) {
            res++;
            ed = range[i].r;
        } else ed = min(ed, range[i].r);
    }
    cout << res << endl;

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 310;

int f[N][N], g[N][N];
int n, m;

int dp(int x, int y) {
    if (f[x][y] != -1) return f[x][y];
    f[x][y] = 1;

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (g[a][b] < g[x][y]) f[x][y] = max(f[x][y], dp(a, b) + 1);
    }
    return f[x][y];
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];

    memset(f, -1, sizeof f);        
    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            res = max(res, dp(i, j));
    cout << res << endl;

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 6010;

int f[N][2];
int e[N], ne[N], h[N], idx;
bool st[N];
int w[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
    f[u][1] = w[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(b, a);
        st[a] = true;
    }

    int root = 1;
    while (st[root]) root++;
    dfs(root);

    cout << max(f[root][0], f[root][1]) << endl;

    return 0;
}