第 1 章 基础算法

// 结构体多关键字排序。洛谷 P1093 [NOIP2007 普及组] 奖学金：
// 按总分从高到低排；总分相同，语文高的在前；还相同，学号小的在前。输出前 5 名的学号和总分。
#include <bits/stdc++.h>
using namespace std;

struct Student {
    int id, chinese, total;
};

// 比较函数回答一个问题：“a 是否必须排在 b 的前面？”
// 两个元素一样时必须返回 false，所以只能用 < 和 >，不能用 <= 和 >=。
bool cmp(const Student &a, const Student &b) {
    if (a.total != b.total) return a.total > b.total;          // 第一关键字：总分，大的在前
    if (a.chinese != b.chinese) return a.chinese > b.chinese;  // 第二关键字：语文，大的在前
    return a.id < b.id;                                        // 第三关键字：学号，小的在前
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Student> s(n);
    for (int i = 0; i < n; i++) {
        int c, m, e;
        cin >> c >> m >> e;
        s[i].id = i + 1;  // 排序会打乱位置，原来的编号要自己存下来
        s[i].chinese = c;
        s[i].total = c + m + e;
    }
    sort(s.begin(), s.end(), cmp);
    for (int i = 0; i < 5 && i < n; i++) cout << s[i].id << ' ' << s[i].total << '\n';
    return 0;
}

// 二分查找。洛谷 P2249 【深基13.例1】查找：
// 在从小到大排好的数列里，对每个询问输出它第一次出现的位置（从 1 数起），没有就输出 -1。
#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int n, m, a[N];

// 返回第一个满足 a[i] >= x 的下标；如果所有数都小于 x，返回 n + 1。
// 固定写法：mid 满足条件就记进 ans、再往左找更靠前的；不满足就往右找。
int first_at_least(int x) {
    int l = 1, r = n, ans = n + 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (m--) {
        int x;
        cin >> x;
        int pos = first_at_least(x);  // 等价于 lower_bound(a + 1, a + n + 1, x) - a
        cout << ((pos <= n && a[pos] == x) ? pos : -1) << ' ';  // 先判越界，再判是不是 x
    }
    cout << '\n';
    return 0;
}

// 二分答案。洛谷 P2678 [NOIP2015 提高组] 跳石头：
// 起点在 0，终点在 L，中间有 n 块石头。最多移走 m 块，让“最短的一跳”尽量长，输出这个最大值。
#include <bits/stdc++.h>
using namespace std;

const int N = 50005;
int L, n, m, d[N];

// 判定：能不能做到每一跳都不短于 x？
// 从左到右贪心：离上一块留下的石头不足 x 的，就移走。
bool check(int x) {
    int removed = 0, last = 0;          // last：上一块留下的石头的位置，一开始是起点
    for (int i = 1; i <= n + 1; i++) {  // d[n + 1] 是终点
        if (d[i] - last < x) removed++;  // 太近，移走（终点太近时，相当于移走 last 那一块，次数一样）
        else last = d[i];
    }
    return removed <= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> L >> n >> m;
    for (int i = 1; i <= n; i++) cin >> d[i];
    d[n + 1] = L;
    // x 越大越难做到：check 的结果形如 真 真 真 假 假，要找最后一个“真”
    int l = 1, r = L, ans = 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;    // mid 可行，记下来，再试更大的
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];  // 预处理
long long sum = s[r] - s[l - 1];                       // a[l..r] 的和

// 二维前缀和：O(nm) 预处理，之后 O(1) 回答任意子矩形的和。
// 输入：n m q，接着 n 行 m 列的矩阵，再 q 个询问 r1 c1 r2 c2（左上角和右下角的行、列）。
// 输出：每个询问的子矩形元素之和。
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
long long s[N][N];  // s[i][j]：第 1..i 行、第 1..j 列这一整块的和。下标从 1 开始，第 0 行和第 0 列都是 0

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a;  // 上 + 左 - 左上（加重了）+ 自己
        }
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        // 大块 - 上面多的 - 左面多的 + 左上角（减重了）
        cout << s[r2][c2] - s[r1 - 1][c2] - s[r2][c1 - 1] + s[r1 - 1][c1 - 1] << '\n';
    }
    return 0;
}

// 差分：把“一段区间整体加一个数”变成只改两个位置，全部改完后做一次前缀和还原。
// 洛谷 P2367 语文成绩：n 个成绩，p 次操作“第 x 到第 y 个人都加 z 分”，输出最后的最低分。
#include <bits/stdc++.h>
using namespace std;

const int N = 5000005;
long long d[N];  // d[i] = a[i] - a[i-1]；它的前缀和 d[1] + ... + d[i] 就是 a[i]

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, p;
    cin >> n >> p;
    int last = 0;  // 上一个人的成绩
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        d[i] = a - last;
        last = a;
    }
    while (p--) {
        int x, y, z;
        cin >> x >> y >> z;
        d[x] += z;      // 从第 x 个开始，后面的都加 z
        d[y + 1] -= z;  // 到第 y + 1 个取消。y 可以等于 n，所以数组要多开一位
    }
    long long cur = 0, lowest = LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        cur += d[i];  // 还原：cur 就是修改之后的 a[i]
        lowest = min(lowest, cur);
    }
    cout << lowest << '\n';
    return 0;
}

// 双指针（滑动窗口）。模型同 CSP-S 2026 T1 能量水晶：
// n 个数，每次操作把某个数加 1，最多操作 m 次，问最多能让多少个数变得相等。输入 n m 和 n 个数。
// 排序之后，选中的一定是连续的一段，都补到这一段的最大值；段越长花费越大，所以可以用双指针。
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
long long a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int best = 0;
    long long cost = 0;  // 把窗口 [l, r] 里的数都补到 a[r]，需要操作多少次
    for (int r = 1, l = 1; r <= n; r++) {
        cost += (r - l) * (a[r] - a[r - 1]);  // 目标从 a[r-1] 升到 a[r]：窗口里原有的 r - l 个数各多补这么多
        while (cost > m) {                    // 超支了：把最小的 a[l] 移出窗口
            cost -= a[r] - a[l];
            l++;
        }
        best = max(best, r - l + 1);  // 此时 [l, r] 是以 r 为右端的最长合法窗口
    }
    cout << best << '\n';
    return 0;
}

for (r = 1, l = 1; r <= n; r++) {
    把 a[r] 加入窗口;
    while (窗口不合法) { 把 a[l] 移出窗口; l++; }
    此时 [l, r] 是以 r 为右端的最长合法窗口，用它更新答案;
}

// 离散化：把很大、很分散的数值换成 1..k 的排名，大小关系不变，之后就能当数组下标用。
// 输入 n 和 n 个整数；输出不同的值有几个，以及每个数的排名（最小的是 1，相同的数排名相同）。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> vals(a);                                       // 第一步：复制一份
    sort(vals.begin(), vals.end());                            // 第二步：排序
    vals.erase(unique(vals.begin(), vals.end()), vals.end());  // 第三步：去重
    cout << (int)vals.size() << '\n';
    for (int i = 0; i < n; i++) {
        int rk = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;  // 第四步：二分查排名
        cout << rk << ' ';  // 需要原值时用 vals[rk - 1] 取回来
    }
    cout << '\n';
    return 0;
}

// 区间调度（贪心）。洛谷 P1803 凌乱的yyy / 线段覆盖：
// n 场比赛各有开始时间和结束时间，同一时刻只能参加一场，问最多能参加几场。
// 贪心：按结束时间从早到晚排序，能参加就参加。结束得越早，留给后面的时间越多。
#include <bits/stdc++.h>
using namespace std;

struct Seg {
    int l, r;
};

bool cmp(const Seg &a, const Seg &b) { return a.r < b.r; }  // 按结束时间排，不是按开始时间

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Seg> s(n);
    for (int i = 0; i < n; i++) cin >> s[i].l >> s[i].r;
    sort(s.begin(), s.end(), cmp);
    int cnt = 0, last = INT_MIN;  // last：上一场参加的比赛的结束时间
    for (int i = 0; i < n; i++)
        if (s[i].l >= last) {  // 上一场已经结束（刚好结束也行），就参加这一场
            cnt++;
            last = s[i].r;
        }
    cout << cnt << '\n';
    return 0;
}

// 反悔贪心（堆）。洛谷 P2949 [USACO09OPEN] Work Scheduling G：
// n 个工作，每个要花 1 单位时间，第 i 个必须在时刻 d_i 之前做完，报酬 p_i。求最大总报酬。
// 做法：按截止时间从早到晚考虑，先接下来；接的数量超过截止时间了，就反悔，退掉报酬最低的那个。
#include <bits/stdc++.h>
using namespace std;

struct Job {
    int d, p;
};

bool cmp(const Job &a, const Job &b) { return a.d < b.d; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Job> job(n);
    for (int i = 0; i < n; i++) cin >> job[i].d >> job[i].p;
    sort(job.begin(), job.end(), cmp);
    priority_queue<int, vector<int>, greater<int> > chosen;  // 小根堆：已接工作的报酬，堆顶是最低的
    long long total = 0;
    for (int i = 0; i < n; i++) {
        chosen.push(job[i].p);  // 先接下
        total += job[i].p;
        if ((int)chosen.size() > job[i].d) {  // 时刻 d 之前最多做 d 个，超了就退掉最不值的
            total -= chosen.top();
            chosen.pop();
        }
    }
    cout << total << '\n';
    return 0;
}