贪心基础：排序型贪心

// 排队接水 —— 全排列枚举：n! 种排队顺序，一种一种试过去
//
// 为什么要有这份代码：
// 这一章的正解只有一句 sort，短到让人不敢信 —— 「凭什么按接水时间从小到大排就是最优的？」
// 所以先把「所有顺序都试一遍」老老实实写出来。它慢，但它**绝对不会错**。
// 后面对拍的标准答案就是它：先确认正解是**对的**，再谈它快不快。
//
// 题意：n 个人排队接水，第 i 个人接水要 t[i] 分钟（一个水龙头，一次只能接一个人）。
//       排在第 k 位的人要等前面 k-1 个人全部接完 —— 他的等待时间就是前面那些 t 的和。
//       求「所有人等待时间之和」的最小值。
//
// 输入：第一行 n，第二行 n 个数 t[1..n]
// 输出：最小的总等待时间
//
// 复杂度 O(n! × n)。n = 10 已经要三千多万次加法，n = 12 就基本跑不完了 ——
// 这正是我们需要贪心的理由。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

    // next_permutation 要求从最小的排列开始，才能枚举到全部 n! 种
    sort(t.begin(), t.end());

    long long best = LLONG_MAX;
    do {
        // 一个人一个人地过：wait 是「轮到他时已经过去了多久」，也就是他的等待时间
        long long total = 0, wait = 0;
        for (int i = 0; i < n; i++) {
            total += wait;
            wait += t[i];
        }
        best = min(best, total);
    } while (next_permutation(t.begin(), t.end()));

    cout << best << "\n";
    return 0;
}

// 排队接水 —— 把「交换论证」真的跑一遍给你看
//
// 为什么要有这份代码：
// 交换论证是一段推导，写在纸上很容易看过去就忘。这份代码把它变成可以观察的事实：
// 从你给的任意顺序出发，每次找到**相邻的一对「慢的在前、快的在后」**就交换它们，
// 并打印总等待时间少了多少。
//
// 你会看到两件事：
//   1. 每一次交换，总等待时间**正好**减少 a − b 分钟（a 是前面那个人，b 是后面那个）。
//      不是「大概」，是分毫不差 —— 而且和这对人站在第几位完全无关。
//   2. 交换到再也找不到这样的一对为止，顺序恰好变成了升序，总等待时间就是 fast.cpp 的答案。
//
// 于是「升序最优」就不再是一句口号：任何非升序的顺序，都能被一路交换着改进到升序。
//
// 顺带一个彩蛋：这个「反复交换相邻逆序对」的过程就是**冒泡排序**（第 10 章），
// 而交换的次数正好是**逆序对个数**（第 11 章）—— 因为交换一对相邻逆序，
// 逆序对个数不多不少刚好减 1。程序最后会把这两个数字并排打给你看。
//
// 输入：第一行 n，第二行 n 个数（**按你想要的排队顺序给**，这里不会先排序）
// 输出：每一次交换的明细 + 最后的核对

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

// 给定排队顺序，算总等待时间：一个人一个人过（和 brute.cpp / fast.cpp 里的循环一样）
static long long waitSum(const vector<long long>& a) {
    long long total = 0, wait = 0;
    for (size_t i = 0; i < a.size(); i++) {
        total += wait;
        wait += a[i];
    }
    return total;
}

static string joinAll(const vector<long long>& a) {
    string s;
    for (size_t i = 0; i < a.size(); i++) {
        if (i) s += ' ';
        s += to_string(a[i]);
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // 先老实数一遍逆序对（O(n²)，第 11 章的暴力版），留到最后核对
    long long inv = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j]) inv++;

    long long total = waitSum(a);
    cout << "初始顺序   : " << joinAll(a) << "\n";
    cout << "初始总等待 : " << total << "\n\n";

    long long swaps = 0;
    while (true) {
        // 从左到右找第一对「慢的在前、快的在后」
        int k = -1;
        for (int i = 0; i + 1 < n; i++)
            if (a[i] > a[i + 1]) { k = i; break; }
        if (k < 0) break;                       // 找不到了 —— 已经是升序

        long long x = a[k], y = a[k + 1];
        swap(a[k], a[k + 1]);
        long long now = waitSum(a);             // 交换后重新老实算一遍，不用公式
        swaps++;

        cout << "#" << setw(2) << swaps
             << "  交换第 " << k + 1 << " 位和第 " << k + 2 << " 位（" << x << " 和 " << y << "）"
             << "：总等待 " << total << " → " << now
             << "，少了 " << total - now
             << "　而 a − b = " << x - y
             << (total - now == x - y ? "  ✓ 正好相等" : "  ✗ 对不上！")
             << "\n     此刻队伍：" << joinAll(a) << "\n";
        total = now;
    }

    cout << "\n再也找不到「慢的排在快的前面」的相邻一对了，队伍已经是升序。\n";
    cout << "共交换 " << swaps << " 次，最终总等待 " << total << "\n";
    cout << "原序列的逆序对个数 = " << inv
         << (inv == swaps ? "　—— 和交换次数一模一样（第 11 章）\n"
                          : "　—— 居然和交换次数不一样，那说明这份代码写错了\n");
    return 0;
}

// 排队接水 —— 正解：把 t 从小到大排序，就完了
//
// 和 brute.cpp 比一比：**算总等待时间的那个循环一模一样，一个字都没改**。
// 唯一的区别是这里只算了一种顺序（升序），而 brute.cpp 算了 n! 种。
//
// ★ 凭什么升序就是最优的？—— 交换论证（跑一下 swap.cpp 亲眼看）：
//
//   设某个顺序里，相邻的两个人接水时间是 a、b，且 a > b（也就是「慢的排在快的前面」）。
//   把这两个人交换一下，总等待时间的变化是多少？
//
//   假设他们站在第 k、k+1 位。排在第 k 位的人，他的接水时间会被后面 (n-k) 个人等；
//   第 k+1 位的会被 (n-k-1) 个人等。于是
//       交换前 = (n-k)·a + (n-k-1)·b
//       交换后 = (n-k)·b + (n-k-1)·a
//       交换后 − 交换前 = (b − a)·[(n-k) − (n-k-1)] = b − a
//
//   b − a < 0，所以**总等待时间正好减少 a − b 分钟，而且和他们站在哪个位置无关**。
//
//   结论：只要还存在「慢的排在快的前面」的相邻一对，就一定能交换出更优的解。
//   所以最优解里不可能存在这样的一对 —— 那就只能是升序。
//
// 复杂度 O(n log n)，瓶颈全在排序上。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

    sort(t.begin(), t.end());          // ★ 整个算法就是这一行

    // 下面这段和 brute.cpp 里的一字不差
    long long total = 0, wait = 0;
    for (int i = 0; i < n; i++) {
        total += wait;                 // 这个人要等前面所有人接完
        wait += t[i];                  // 然后轮到他，后面的人再多等 t[i]
    }

    cout << total << "\n";             // 用 long long：n = 1e5、t = 1e3 时会超 int
    return 0;
}

// 区间调度 —— 四种排序方式并排跑，看看谁是对的
//
// 为什么要有这份代码：
// 「按右端点排序」这句话，光背是没用的，你必须知道**另外两种听起来同样合理的排法错在哪**。
// 这份代码用同一组数据把四种做法并排跑出来：
//
//   ① 按左端点从早到晚 —— 「早点开始，能多参加几场」→ 错。
//      一场从早开到晚的比赛开始得最早，却把整天都占了。
//   ② 按区间从短到长   —— 「挑短的，占的时间少」→ 也错。
//      一场很短的比赛可能正好卡在两场长比赛的中间，一个换掉俩。
//   ③ 按右端点从早到晚 —— 正解。结束得越早，留给后面的时间越多。
//   ④ 2ⁿ 枚举子集     —— 一定最优，用来当尺子。
//
// 三种贪心用的是**同一个函数**，只是喂进去的顺序不同 —— 这样对比才公平：
// 差别百分之百来自「怎么排序」，不来自别的地方。
//
// 注意选取时的判断：按给定顺序一个一个看，只要**和已经选中的任何一场都不冲突**就选。
// （对③来说「和最后选的那场不冲突」就够了，因为它的结束时间是递增的；
//   但①②不成立，所以这里统一写成和所有已选的比 —— 老实但公平。）
//
// 输入格式和 itvFast.cpp 一样。输出是一张四行的表。
// 想找一组能打假①②的数据？跑 itvGen.cpp 造，或者直接用第 20 章的对拍器批量找。

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

struct Seg { long long l, r; };

// 按 order 给出的顺序逐个考察，不冲突就选。返回选出的场数。
static int greedyBy(const vector<Seg>& a, const vector<int>& order) {
    vector<Seg> picked;
    for (int idx : order) {
        bool ok = true;
        for (const Seg& p : picked)
            if (a[idx].l < p.r && p.l < a[idx].r) { ok = false; break; }   // 有重叠部分才算冲突
        if (ok) picked.push_back(a[idx]);
    }
    return (int)picked.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<Seg> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;

    vector<int> id(n);
    for (int i = 0; i < n; i++) id[i] = i;

    vector<int> byL = id, byLen = id, byR = id;
    sort(byL.begin(), byL.end(), [&](int x, int y) {
        return a[x].l != a[y].l ? a[x].l < a[y].l : a[x].r < a[y].r;
    });
    sort(byLen.begin(), byLen.end(), [&](int x, int y) {
        long long dx = a[x].r - a[x].l, dy = a[y].r - a[y].l;
        return dx != dy ? dx < dy : a[x].l < a[y].l;
    });
    sort(byR.begin(), byR.end(), [&](int x, int y) {
        return a[x].r != a[y].r ? a[x].r < a[y].r : a[x].l < a[y].l;
    });

    // ④ 老实枚举子集当尺子（和 itvBrute.cpp 同一套逻辑）
    vector<Seg> s = a;
    // 左端点相同时必须再按右端点排（短的在前）。少了这一句，[12,13] 和 [12,12] 这种
    // 「长的排在短的前面」会让下面「只和上一个选中的比」判错，最优解会算小 ——
    // 这不是假想，是这一章的交叉验证真的抓到过的一次事故。
    sort(s.begin(), s.end(), [](const Seg& x, const Seg& y) {
        return x.l != y.l ? x.l < y.l : x.r < y.r;
    });
    int best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int cnt = 0;
        long long lastEnd = LLONG_MIN;
        bool ok = true;
        for (int i = 0; i < n && ok; i++) {
            if (!(mask >> i & 1)) continue;
            if (s[i].l < lastEnd) ok = false;
            else { lastEnd = s[i].r; cnt++; }
        }
        if (ok) best = max(best, cnt);
    }

    int r1 = greedyBy(a, byL), r2 = greedyBy(a, byLen), r3 = greedyBy(a, byR);

    cout << "策略                          选出的场数\n";
    cout << "① 按左端点从早到晚              " << r1 << (r1 == best ? "" : "   ← 比最优少") << "\n";
    cout << "② 按区间从短到长                " << r2 << (r2 == best ? "" : "   ← 比最优少") << "\n";
    cout << "③ 按右端点从早到晚（正解）      " << r3 << (r3 == best ? "" : "   ← 居然不是最优？那是代码写错了") << "\n";
    cout << "④ 暴力枚举子集（一定最优）      " << best << "\n";

    if (r1 == best && r2 == best)
        cout << "\n这组数据太温柔了，三种排法都蒙对了 —— 换一组再试（错误的贪心不是每次都错）。\n";
    return 0;
}

// 区间调度（线段覆盖）—— 正解：按**右端点**从早到晚排序，能选就选
//
// 题意：n 场比赛，第 i 场占用时间段 [l, r]。一个人同一时刻只能参加一场，
//       但**上一场的结束时刻可以正好是下一场的开始时刻**（即 [1,3] 和 [3,5] 不冲突）。
//       最多能参加几场？
//
// ★ 关键一步：按「结束时间」排序，而不是「开始时间」，也不是「持续时间」。
//
//   为什么是结束时间 —— 交换论证（和排队接水是同一套思路）：
//   设最优解按时间排好后第一场是 X，而贪心选的第一场是 Y（Y 是全场结束最早的）。
//   那么 Y.r <= X.r。把最优解里的 X 换成 Y：Y 结束得不比 X 晚，
//   所以原来能接在 X 后面的那些场次，现在照样能接在 Y 后面 ——
//   **场数一个没少，而且第一场和贪心一致了**。
//   对剩下的部分重复这个论证，就能把最优解一步步「掰」成贪心解，且场数始终不变。
//   所以贪心解和最优解一样多。
//
//   直觉版说法：**结束得越早，留给后面的时间就越多**。而「开始得早」「时间短」
//   都不能保证这一点 —— 一场从头开到尾的比赛开始得最早，却把整天都占了。
//   （错误的那几种排法值多少分，跑 itvWrong.cpp 看表。）
//
// 输入：第一行 n，接下来 n 行每行两个数 l r
// 输出：最多能参加的场数
//
// 复杂度 O(n log n)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<long long, long long>> a(n);       // 存成 (r, l)，直接按 r 排
    for (int i = 0; i < n; i++) {
        long long l, r;
        cin >> l >> r;
        a[i] = {r, l};
    }

    sort(a.begin(), a.end());                      // ★ 按右端点从早到晚

    int cnt = 0;
    long long lastEnd = LLONG_MIN;                 // 上一场的结束时刻
    for (int i = 0; i < n; i++) {
        long long r = a[i].first, l = a[i].second;
        if (l >= lastEnd) {                        // 不冲突（端点重合算不冲突）
            cnt++;
            lastEnd = r;
        }
    }

    cout << cnt << "\n";
    return 0;
}

// 排队接水 —— 正解：把 t 从小到大排序，就完了
//
// 和 brute.cpp 比一比：**算总等待时间的那个循环一模一样，一个字都没改**。
// 唯一的区别是这里只算了一种顺序（升序），而 brute.cpp 算了 n! 种。
//
// ★ 凭什么升序就是最优的？—— 交换论证（跑一下 swap.cpp 亲眼看）：
//
//   设某个顺序里，相邻的两个人接水时间是 a、b，且 a > b（也就是「慢的排在快的前面」）。
//   把这两个人交换一下，总等待时间的变化是多少？
//
//   假设他们站在第 k、k+1 位。排在第 k 位的人，他的接水时间会被后面 (n-k) 个人等；
//   第 k+1 位的会被 (n-k-1) 个人等。于是
//       交换前 = (n-k)·a + (n-k-1)·b
//       交换后 = (n-k)·b + (n-k-1)·a
//       交换后 − 交换前 = (b − a)·[(n-k) − (n-k-1)] = b − a
//
//   b − a < 0，所以**总等待时间正好减少 a − b 分钟，而且和他们站在哪个位置无关**。
//
//   结论：只要还存在「慢的排在快的前面」的相邻一对，就一定能交换出更优的解。
//   所以最优解里不可能存在这样的一对 —— 那就只能是升序。
//
// 复杂度 O(n log n)，瓶颈全在排序上。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

    sort(t.begin(), t.end());          // ★ 整个算法就是这一行

    // 下面这段和 brute.cpp 里的一字不差
    long long total = 0, wait = 0;
    for (int i = 0; i < n; i++) {
        total += wait;                 // 这个人要等前面所有人接完
        wait += t[i];                  // 然后轮到他，后面的人再多等 t[i]
    }

    cout << total << "\n";             // 用 long long：n = 1e5、t = 1e3 时会超 int
    return 0;
}

// 区间调度（线段覆盖）—— 正解：按**右端点**从早到晚排序，能选就选
//
// 题意：n 场比赛，第 i 场占用时间段 [l, r]。一个人同一时刻只能参加一场，
//       但**上一场的结束时刻可以正好是下一场的开始时刻**（即 [1,3] 和 [3,5] 不冲突）。
//       最多能参加几场？
//
// ★ 关键一步：按「结束时间」排序，而不是「开始时间」，也不是「持续时间」。
//
//   为什么是结束时间 —— 交换论证（和排队接水是同一套思路）：
//   设最优解按时间排好后第一场是 X，而贪心选的第一场是 Y（Y 是全场结束最早的）。
//   那么 Y.r <= X.r。把最优解里的 X 换成 Y：Y 结束得不比 X 晚，
//   所以原来能接在 X 后面的那些场次，现在照样能接在 Y 后面 ——
//   **场数一个没少，而且第一场和贪心一致了**。
//   对剩下的部分重复这个论证，就能把最优解一步步「掰」成贪心解，且场数始终不变。
//   所以贪心解和最优解一样多。
//
//   直觉版说法：**结束得越早，留给后面的时间就越多**。而「开始得早」「时间短」
//   都不能保证这一点 —— 一场从头开到尾的比赛开始得最早，却把整天都占了。
//   （错误的那几种排法值多少分，跑 itvWrong.cpp 看表。）
//
// 输入：第一行 n，接下来 n 行每行两个数 l r
// 输出：最多能参加的场数
//
// 复杂度 O(n log n)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<long long, long long>> a(n);       // 存成 (r, l)，直接按 r 排
    for (int i = 0; i < n; i++) {
        long long l, r;
        cin >> l >> r;
        a[i] = {r, l};
    }

    sort(a.begin(), a.end());                      // ★ 按右端点从早到晚

    int cnt = 0;
    long long lastEnd = LLONG_MIN;                 // 上一场的结束时刻
    for (int i = 0; i < n; i++) {
        long long r = a[i].first, l = a[i].second;
        if (l >= lastEnd) {                        // 不冲突（端点重合算不冲突）
            cnt++;
            lastEnd = r;
        }
    }

    cout << cnt << "\n";
    return 0;
}