[ICPC2020济南D] Fight against involution

[ICPC2020济南D] Fight against involution - 贪心

Description

有一门课程n个学生选，期末要写一篇论文每个同学写的字数有一个下限和一个上限，课程的成绩是按学生字数的排名来给分的，排名越高分数越高，每个同学都想得到更高的成绩，而且他们都想写最少字数，那么在满足每个同学不能比原计划分数低的情况下求出所有同学总共要写的最少字数。

Solution

我们按照 ri 相同的一段一段来决策，那么每段内的值显然是一样的，并且一定不能小于 ri 更小者的值，这样已经可以做了，但为了实现方便，我们可以——

按 ri 升序为第一关键字，li 降序为第二关键字排序，每到一个人，他的字数在上一个人的字数和自己的 li 之间取 max

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

#define int long long

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

    struct item
    {
        int l, r;
        bool operator<(const item &rhs) const
        {
            if (r != rhs.r)
                return r < rhs.r;
            else
                return l > rhs.l;
        }
    };

    vector<item> items(n);
    for (int i = 0; i < n; i++)
        cin >> items[i].l >> items[i].r;

    sort(items.begin(), items.end());

    int now = 0;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        now = max(now, items[i].l);
        ans += now;
    }

    cout << ans << endl;
}