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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<long long> g(n);
    for (long long &x : g) cin >> x;

    // 总代价 = 每对逆序对 (i,j)（i<j，g[i]>g[j]）的 g[i]+g[j] 之和
    long long totalCost = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (g[i] > g[j]) {
                totalCost += g[i] + g[j];  // 这个逆序对的代价
            }
        }
    }

    cout << totalCost << "\n";
    return 0;
}
// 时间：O(N²) — N ≤ 10^5 时用归并排序逆序对计数（O(N log N)）

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, c;
    cin >> n >> c;

    vector<int> t(n);
    for (int &x : t) cin >> x;
    sort(t.begin(), t.end());  // 按出发时间顺序处理

    int ans = 0;
    // 每 c 头奶牛一组处理
    for (int i = 0; i < n; i += c) {
        // 这批奶牛中最早的是 t[i]
        ans = max(ans, t[i]);  // 这批出发时间至少要等最早的奶牛准备好
        ans++;  // 过路需要 1 个时间单位
    }

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

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

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

    vector<int> A(n), B(n);
    for (int &x : A) cin >> x;
    for (int &x : B) cin >> x;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += min(A[i], B[i]);  // 第 i 小的与第 i 小的配对
    }

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

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

int n, m, c;
vector<long long> cows;   // 按到达时间排序

// 最大等待时间 <= maxWait 时能否调度所有奶牛？
bool canDo(long long maxWait) {
    int busesUsed = 0;
    int i = 0;  // 当前奶牛下标

    while (i < n) {
        busesUsed++;
        if (busesUsed > m) return false;  // 公共汽车不够用了

        // 该车从奶牛 i 开始服务
        // 车必须在 cows[i] + maxWait 之前出发
        long long depart = cows[i] + maxWait;

        // 尽量多地装奶牛（容量 c，到达时间 ≤ 出发时间）
        int count = 0;
        while (i < n && count < c && cows[i] <= depart) {
            i++;
            count++;
        }
    }

    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> c;
    cows.resize(n);
    for (long long &x : cows) cin >> x;
    sort(cows.begin(), cows.end());

    // 对最大等待时间二分
    long long lo = 0, hi = 1e14;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }

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

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

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    long long pos[3] = {a, b, c};
    sort(pos, pos + 3);
    a = pos[0]; b = pos[1]; c = pos[2];

    // 0 次移动：已是连续
    if (c - a == 2) { cout << 0; return 0; }

    // 1 次移动：检查各情况
    bool one_move = false;

    // (b,c) 对保留：移动 a
    if (c - b == 1 || c - b == 2) one_move = true;
    // (a,b) 对保留：移动 c
    if (b - a == 1 || b - a == 2) one_move = true;
    // (a,c) 对保留：移动 b（需 c-a==3）
    if (c - a == 3) one_move = true;

    if (one_move) { cout << 1; return 0; }

    cout << 2;
    return 0;
}

排序位置，然后用 lower_bound / upper_bound 二分搜索统计 [L, R] 内的元素。这道题练习「排序 + 二分搜索」思维——大多数贪心算法的第一步。

排序后，[L, R] 内的数量 = upper_bound(R) - lower_bound(L)。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<int> pos(n);
    for (int &x : pos) cin >> x;
    sort(pos.begin(), pos.end());  // 关键：先排序以支持二分搜索

    while (q--) {
        int l, r;
        cin >> l >> r;

        auto lo = lower_bound(pos.begin(), pos.end(), l);
        auto hi = upper_bound(pos.begin(), pos.end(), r);

        cout << (hi - lo) << "\n";
    }

    return 0;
}
// 时间复杂度：O(N log N + Q log N)

核心思路： 找队尾已经有序的最长后缀（连续的 k, k+1, ..., N）。这些奶牛不需要移动。答案 = N − 后缀长度。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> cows(n);
    for (int &x : cows) cin >> x;

    // 找最长已排序后缀：cows[i], cows[i+1], ..., cows[n-1]
    // 条件：cows[i] + 1 == cows[i+1]（连续递增）
    int keep = 1;  // 至少最后一头奶牛留下
    for (int i = n - 2; i >= 0; i--) {
        if (cows[i] + 1 == cows[i + 1]) {
            keep++;
        } else {
            break;  // 后缀必须连续——遇到第一个断点就停
        }
    }

    cout << n - keep << "\n";
    return 0;
}
// 时间复杂度：O(N)

关键公式：ans = max(任务总数, (maxCount-1)*(k+1) + countMax)

其中 maxCount = 出现次数最多的任务的频率。

贪心策略：每个「帧」（每 k+1 个时间单位）先填最频繁的剩余任务。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> freq(26, 0);
    for (int i = 0; i < n; i++) {
        char c; cin >> c;
        freq[c - 'A']++;
    }

    int maxCount = *max_element(freq.begin(), freq.end());
    int countMax = count(freq.begin(), freq.end(), maxCount);

    int ans = max(n, (maxCount - 1) * (k + 1) + countMax);

    cout << ans << "\n";
    return 0;
}
// 时间复杂度：O(N)

用优先队列（按资历下标最小堆）模拟。维护已到达但未喝水的奶牛的「等待队列」。每次设备空闲时，从等待队列中取资历最高（下标最小）的奶牛。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // {到达时间, 原始下标（资历）, 喝水时长}
    vector<tuple<int,int,int>> cows(n);
    for (int i = 0; i < n; i++) {
        int a, t;
        cin >> a >> t;
        cows[i] = {a, i, t};  // 原始下标 i = 资历（0 = 最高资历）
    }

    sort(cows.begin(), cows.end());  // 按到达时间排序

    // 最小堆：{资历下标, 到达时间, 喝水时长}——下标最小优先级最高
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> waiting;

    int curTime = 0;  // 设备下次空闲的时间
    int maxWait = 0;
    int idx = 0;

    while (idx < n || !waiting.empty()) {
        // 将所有在 curTime 之前到达的奶牛加入等待队列
        while (idx < n && get<0>(cows[idx]) <= curTime) {
            auto [a, seniority, t] = cows[idx];
            waiting.push({seniority, a, t});
            idx++;
        }

        if (waiting.empty()) {
            curTime = get<0>(cows[idx]);
            continue;
        }

        // 服务资历最高（下标最小）的等待奶牛
        auto [seniority, arrTime, drinkTime] = waiting.top();
        waiting.pop();

        int waitTime = curTime - arrTime;
        maxWait = max(maxWait, waitTime);
        curTime += drinkTime;
    }

    cout << maxWait << "\n";
    return 0;
}
// 时间复杂度：O(N log N)

为什么贪心失败？

• 按利润排序取最大值？不行。反例：(s=1,e=10,p=100) vs (s=1,e=3,p=50)+(s=4,e=7,p=60)——后者总计 110。
• 按最早结束时间？不行。贪心可能选利润为 1 的短工作，错过利润 100 的长工作。
• 贪心无法同时优化「早结束」和「最大利润」。这是加权区间调度——DP 问题。

DP 做法：

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<tuple<int,int,int>> jobs(n);  // {结束时间, 开始时间, 利润}
    for (int i = 0; i < n; i++) {
        int s, e, p;
        cin >> s >> e >> p;
        jobs[i] = {e, s, p};
    }

    sort(jobs.begin(), jobs.end());  // 按结束时间排序

    vector<int> ends;
    for (auto [e, s, p] : jobs) ends.push_back(e);

    vector<long long> dp(n + 1, 0);  // dp[i]：前 i 个工作的最大利润（1-indexed）

    for (int i = 1; i <= n; i++) {
        auto [e, s, p] = jobs[i - 1];

        // 二分搜索：找最后一个结束时间 <= s[i] 的工作（不重叠）
        int lo = 0, hi = i - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (ends[mid - 1] <= s) lo = mid;
            else hi = mid - 1;
        }

        dp[i] = max(dp[i - 1], dp[lo] + p);  // 跳过 vs 选取
    }

    cout << dp[n] << "\n";
    return 0;
}
// 时间复杂度：O(N log N)

教训： 选择不重叠区间时，若区间有权重（利润），贪心不起作用——用 DP。只有当所有权重相等（最大化数量）时，才能简化为贪心。