1. 处理元素时有没有自然的「顺序」或「优先级」？
   （如：按截止时间、结束时间、比率、大小排序……）
        ↓ 有
2. 能证明局部最优选择在全局上是安全的吗？
   （交换论证：把贪心选择与任何其他选择互换，永远不会更好）
        ↓ 能
3. 能找到贪心失败的小反例吗？
        ↓ 找不到反例
   → 贪心很可能正确。实现并验证。
        ↓ 找到反例
   → 贪心失败。考虑 DP 或其他方法。

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

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

    int n;
    cin >> n;

    vector<pair<int,int>> jobs(n);  // {t, w}
    for (auto &[t, w] : jobs) cin >> t >> w;

    // 按 w/t 比值降序排序（比值更高的先做）
    sort(jobs.begin(), jobs.end(), [](const auto &a, const auto &b) {
        // a.second/a.first > b.second/b.first  →  a.second * b.first > b.second * a.first
        return (long long)a.second * b.first > (long long)b.second * a.first;
    });

    long long total = 0, curTime = 0;
    for (auto [t, w] : jobs) {
        curTime += t;
        total += (long long)w * curTime;
    }

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

// 活动选择 — O(N log N)
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<pair<int,int>> activities(n);  // {结束时间, 开始时间}
    for (int i = 0; i < n; i++) {
        int s, f;
        cin >> s >> f;
        activities[i] = {f, s};  // 按结束时间排序
    }

    sort(activities.begin(), activities.end());  // ← 关键：按结束时间排序

    int count = 0;
    int lastEnd = -1;  // 最后一个选定活动的结束时间

    for (auto [f, s] : activities) {
        if (s >= lastEnd) {      // 该活动在上一个结束后才开始
            count++;
            lastEnd = f;         // 更新最后结束时间
        }
    }

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

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

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

    int n;
    cin >> n;
    vector<pair<int,int>> intervals(n);  // {右端点, 左端点}
    for (auto &[r, l] : intervals) cin >> l >> r;

    sort(intervals.begin(), intervals.end());  // 按右端点排序

    int points = 0;
    long long lastPoint = LLONG_MIN;

    for (auto [r, l] : intervals) {
        if (lastPoint < l) {          // 当前点不覆盖该区间
            lastPoint = r;            // 在右端放新点
            points++;
        }
    }

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

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

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

    int T, n;
    cin >> T >> n;

    vector<pair<int,int>> intervals(n);
    for (auto &[l, r] : intervals) cin >> l >> r;

    sort(intervals.begin(), intervals.end());  // 按左端点排序

    int covered = 0;    // 当前已覆盖到 'covered'
    int count = 0;
    int i = 0;

    while (covered < T) {
        int farthest = covered;

        // 在左端点 <= covered 的所有区间中，找最远的右端点
        while (i < n && intervals[i].first <= covered) {
            farthest = max(farthest, intervals[i].second);
            i++;
        }

        if (farthest == covered) {
            // 没有区间能延伸覆盖——不可能
            cout << "Impossible\n";
            return 0;
        }

        covered = farthest;
        count++;
    }

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

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

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

    vector<pair<int,int>> jobs(n);  // {截止时间, 处理时间}
    for (int i = 0; i < n; i++) cin >> jobs[i].second >> jobs[i].first;

    sort(jobs.begin(), jobs.end());  // 按截止时间排序

    int time = 0;
    int maxLateness = 0;

    for (auto [deadline, proc] : jobs) {
        time += proc;                          // 该作业的完成时间
        int lateness = max(0, time - deadline); // 延迟多久？
        maxLateness = max(maxLateness, lateness);
    }

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

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

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

    priority_queue<long long, vector<long long>, greater<long long>> pq;  // 最小堆
    for (int i = 0; i < n; i++) {
        long long f; cin >> f;
        pq.push(f);
    }

    long long totalCost = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        totalCost += a + b;  // 合并 a 和 b 的代价
        pq.push(a + b);      // 合并后的组频率为 a+b
    }

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

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

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

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

    sort(t.begin(), t.end());  // SJF：按处理时间升序

    long long totalCompletion = 0;
    long long curTime = 0;
    for (int i = 0; i < n; i++) {
        curTime += t[i];
        totalCompletion += curTime;
    }

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

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

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

    int n;
    cin >> n;
    vector<string> nums(n);
    for (string &s : nums) cin >> s;

    // 自定义排序：a+b > b+a 时 a 排在前面
    sort(nums.begin(), nums.end(), [](const string &a, const string &b) {
        return a + b > b + a;
    });

    // 边界情况：全为零
    if (nums[0] == "0") {
        cout << "0\n";
        return 0;
    }

    string result = "";
    for (const string &s : nums) result += s;
    cout << result << "\n";
    return 0;
}
// 时间复杂度：O(N log N · L)，L = 最大数字位数

// 最大化 sum(A[i] * B[i])
sort(A.begin(), A.end());
sort(B.begin(), B.end());
long long maxSum = 0;
for (int i = 0; i < n; i++) maxSum += (long long)A[i] * B[i];

// 最小化 sum(A[i] * B[i])
sort(A.begin(), A.end());
sort(B.begin(), B.end(), greater<int>());
long long minSum = 0;
for (int i = 0; i < n; i++) minSum += (long long)A[i] * B[i];

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

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

    int n;
    cin >> n;

    vector<int> ability(n), difficulty(n);
    for (int &x : ability) cin >> x;
    for (int &x : difficulty) cin >> x;

    sort(ability.begin(), ability.end());
    sort(difficulty.begin(), difficulty.end());

    // 双指针：贪心地把最弱的有能力工人分配给每个任务
    int completed = 0;
    int i = 0, j = 0;  // i：工人指针，j：任务指针

    while (i < n && j < n) {
        if (ability[i] >= difficulty[j]) {
            // 工人 i 能完成任务 j——匹配
            completed++;
            i++;
            j++;
        } else {
            // 工人 i 太弱——尝试更强的工人
            i++;
        }
    }

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

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

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

    int n;
    cin >> n;

    vector<pair<int,int>> intervals(n);
    for (auto &[l, r] : intervals) cin >> l >> r;

    sort(intervals.begin(), intervals.end());  // 按左端点排序

    vector<pair<int,int>> merged;

    for (auto [l, r] : intervals) {
        if (merged.empty() || l > merged.back().second) {
            // 无重叠——开始新的合并区间
            merged.push_back({l, r});
        } else {
            // 重叠——延伸右端点
            merged.back().second = max(merged.back().second, r);
        }
    }

    cout << merged.size() << " 个合并区间：\n";
    for (auto [l, r] : merged) {
        cout << "[" << l << "," << r << "] ";
    }
    cout << "\n";
    return 0;
}
// 时间复杂度：O(N log N)

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

int main() {
    string num;
    int k;
    cin >> num >> k;

    string stk = "";  // 用字符串作单调栈

    for (char c : num) {
        // 当栈顶大于当前数字且还有删除机会时弹出
        while (k > 0 && !stk.empty() && stk.back() > c) {
            stk.pop_back();
            k--;
        }
        stk.push_back(c);
    }

    // 若还有删除机会，从右端删除
    stk.resize(stk.size() - k);

    // 移除前导零
    int start = 0;
    while (start < (int)stk.size() - 1 && stk[start] == '0') start++;

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

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

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    int jumps = 0;
    int curEnd = 0;    // 当前跳跃能到达的最远位置
    int farthest = 0;  // 目前可到达的最远位置

    for (int i = 0; i < n - 1; i++) {
        farthest = max(farthest, i + A[i]);  // 更新最远可达
        if (i == curEnd) {                   // 到达当前跳跃范围的末尾
            jumps++;
            curEnd = farthest;               // 跳到最远位置
            if (curEnd >= n - 1) break;      // 已经可以到达末尾
        }
    }

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

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

int main() {
    int n;
    cin >> n;
    vector<int> prices(n);
    for (int &x : prices) cin >> x;

    int profit = 0;
    for (int i = 1; i < n; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];  // 捕获每次上涨
        }
    }

    cout << profit << "\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, k;
    cin >> n >> k;

    priority_queue<long long> pq;  // 最大堆
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        pq.push(x);
    }

    long long total = 0;
    for (int i = 0; i < k; i++) {
        long long top = pq.top(); pq.pop();
        if (top <= 0) break;  // 取该元素会损失——停止
        total += top;
        pq.push(-top);        // 插入后悔节点：撤销此操作的代价
    }

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

#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> t(n);
    for (int &x : t) cin >> x;

    sort(t.begin(), t.end(), greater<int>());  // 降序：最长作业优先

    // 最小堆：存储每台机器的当前完成时间（初始全为 0）
    priority_queue<long long, vector<long long>, greater<long long>> machines;
    for (int i = 0; i < k; i++) machines.push(0);

    for (int i = 0; i < n; i++) {
        long long earliest = machines.top(); machines.pop();
        machines.push(earliest + t[i]);  // 将作业分配给最早空闲的机器
    }

    long long makespan = 0;
    while (!machines.empty()) {
        makespan = max(makespan, machines.top());
        machines.pop();
    }

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

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

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

    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());

    int wins = 0;
    int lo = 0, hi = n - 1;    // A 的双端指针（弱端和强端）
    int blo = 0, bhi = n - 1;  // B 的双端指针

    while (lo <= hi) {
        if (A[hi] > B[bhi]) {
            // A 最强打赢 B 最强——赢一场
            wins++;
            hi--;
            bhi--;
        } else {
            // A 最强打不赢 B 最强——用 A 最弱消耗 B 最强
            lo++;
            bhi--;
        }
    }

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

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

int main() {
    int n;
    cin >> n;
    vector<int> rating(n);
    for (int &x : rating) cin >> x;

    vector<int> candy(n, 1);  // 每人至少 1 颗糖

    // 第一遍：满足「比左邻居评分高则多拿」
    for (int i = 1; i < n; i++) {
        if (rating[i] > rating[i - 1])
            candy[i] = candy[i - 1] + 1;
    }

    // 第二遍：满足「比右邻居评分高则多拿」
    for (int i = n - 2; i >= 0; i--) {
        if (rating[i] > rating[i + 1])
            candy[i] = max(candy[i], candy[i + 1] + 1);
    }

    cout << accumulate(candy.begin(), candy.end(), 0) << "\n";
    return 0;
}
// 时间复杂度：O(N)

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

const int MAXBIT = 30;

struct Trie {
    int ch[2];
    Trie() { ch[0] = ch[1] = -1; }
};

vector<Trie> trie(1);

void insert(int x) {
    int node = 0;
    for (int i = MAXBIT; i >= 0; i--) {
        int bit = (x >> i) & 1;
        if (trie[node].ch[bit] == -1) {
            trie[node].ch[bit] = trie.size();
            trie.push_back(Trie());
        }
        node = trie[node].ch[bit];
    }
}

int maxXOR(int x) {
    int node = 0, res = 0;
    for (int i = MAXBIT; i >= 0; i--) {
        int bit = (x >> i) & 1;
        int want = 1 - bit;  // 贪心：尝试对立位使 XOR = 1
        if (trie[node].ch[want] != -1) {
            res |= (1 << i);
            node = trie[node].ch[want];
        } else {
            node = trie[node].ch[bit];
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int &x : nums) cin >> x;

    for (int x : nums) insert(x);

    int ans = 0;
    for (int x : nums) ans = max(ans, maxXOR(x));

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

最少会议室数 = 任意时刻最多重叠的会议数。用最小堆追踪结束时间（每间会议室何时空闲）。对每场新会议，检查最早空闲的会议室能否复用。

核心思路：

按开始时间排序会议，最小堆存储每间会议室的结束时间。对每场新会议：

• 若堆顶（最早结束的会议室）≤ 新会议开始时间 → 复用该会议室
• 否则 → 开新会议室

堆的最终大小就是答案。

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

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

    int n;
    cin >> n;

    vector<pair<int,int>> meetings(n);
    for (int i = 0; i < n; i++)
        cin >> meetings[i].first >> meetings[i].second;

    sort(meetings.begin(), meetings.end());  // 按开始时间排序

    // 最小堆：存储每间使用中会议室的结束时间
    priority_queue<int, vector<int>, greater<int>> pq;

    for (auto [start, end] : meetings) {
        if (!pq.empty() && pq.top() <= start) {
            // 复用最早空闲的会议室
            pq.pop();
        }
        pq.push(end);  // 该会议室被占用到 'end' 时刻
    }

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

核心思路：若总油量 ≥ 总耗油量，则恰好存在一个有效起始站。贪心扫描：每当累计油箱降至零以下，将起始站重置为下一站。

两个关键定理：

1. 可行性： 若 sum(gas) < sum(cost)，无解。
2. 唯一起始站定理： 若有解，每当从站 s 出发的运行油箱变为负数，s 到故障点之间的任何站都不是有效起始点。因此下一个候选站必须紧接在故障点之后。

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

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

    int n;
    cin >> n;

    vector<int> gas(n), cost(n);
    for (int &x : gas) cin >> x;
    for (int &x : cost) cin >> x;

    int totalTank = 0;  // 总净油量（决定可行性）
    int tank = 0;       // 从 'start' 出发的当前油量
    int start = 0;      // 当前候选起始站

    for (int i = 0; i < n; i++) {
        int gain = gas[i] - cost[i];
        tank += gain;
        totalTank += gain;

        if (tank < 0) {
            // 从 'start' 无法到达 i+1 — 重置
            start = i + 1;
            tank = 0;
        }
    }

    if (totalTank < 0) {
        cout << -1 << "\n";  // 无解
    } else {
        cout << start << "\n";
    }
    return 0;
}
// 时间复杂度：O(N)——单次扫描

双指针/事件扫描：将所有到达（+1）和出发（-1）事件合并为一个排序列表，扫描时维护当前站台数。峰值就是答案。注意：相同时间时，出发事件先于到达事件处理（离开的火车先让出站台再占用）。

方法一：事件扫描（推荐）

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

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

    int n;
    cin >> n;

    vector<pair<int,int>> events;  // {时间, 类型}：类型=0 出发，类型=1 到达
    for (int i = 0; i < n; i++) {
        int a, d;
        cin >> a >> d;
        events.push_back({a, 1});   // 到达
        events.push_back({d, 0});   // 出发（类型=0 < 1，相同时间出发先处理）
    }

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

    int platforms = 0, maxPlatforms = 0;
    for (auto [time, type] : events) {
        if (type == 1) platforms++;   // 火车到达
        else platforms--;             // 火车出发
        maxPlatforms = max(maxPlatforms, platforms);
    }

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

方法二：双指针（经典）

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

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

    vector<int> arr(n), dep(n);
    for (int &x : arr) cin >> x;
    for (int &x : dep) cin >> x;

    sort(arr.begin(), arr.end());
    sort(dep.begin(), dep.end());

    int platforms = 1, maxPlatforms = 1;
    int i = 1, j = 0;

    while (i < n && j < n) {
        if (arr[i] <= dep[j]) {
            platforms++;
            i++;
        } else {
            platforms--;
            j++;
        }
        maxPlatforms = max(maxPlatforms, platforms);
    }

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

贪心有效是因为允许取分量。按价值/重量比（单位价值）降序排序，尽可能多地取比率最高的物品直到背包装满。

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

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

    int n;
    double W;
    cin >> n >> W;

    vector<pair<double,double>> items(n);  // {价值, 重量}
    for (int i = 0; i < n; i++)
        cin >> items[i].second >> items[i].first;

    // 按单位价值（v/w）降序排序
    sort(items.begin(), items.end(), [](const auto &a, const auto &b) {
        return a.first / a.second > b.first / b.second;
    });

    double totalValue = 0.0;
    double remaining = W;

    for (auto [v, w] : items) {
        if (remaining <= 0) break;
        if (w <= remaining) {
            totalValue += v;
            remaining -= w;
        } else {
            totalValue += v * (remaining / w);
            remaining = 0;
        }
    }

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

维护 farthest = 目前可到达的最远下标。扫描每个可达位置，更新 farthest。若某时刻 i > farthest，位置 i 不可达——返回 false。

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

bool canJump(vector<int>& A) {
    int n = A.size();
    int farthest = 0;

    for (int i = 0; i < n; i++) {
        if (i > farthest) return false;
        farthest = max(farthest, i + A[i]);
        if (farthest >= n - 1) return true;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;
    cout << (canJump(A) ? "true" : "false") << "\n";
}

为什么贪心正确： 每步不选具体跳跃——只是追踪从当前所有可达位置出发，所有可能跳跃的并集。这等价于同时考虑所有可能的跳跃路径。

贪心策略： 按右端点升序排序。维护 lastPoint（最后一个锚点的位置，初始 −∞）。对每段：若 lastPoint 不在 [L_i, R_i] 内（即 lastPoint < L_i），在 R_i 放一个新锚点（尽量靠右以覆盖更多后续区间）。

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

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

    int n;
    cin >> n;

    vector<pair<int,int>> segs(n);  // {右端点, 左端点}
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        segs[i] = {r, l};
    }

    sort(segs.begin(), segs.end());  // 按右端点排序

    int count = 0;
    long long lastPoint = LLONG_MIN;

    for (auto [r, l] : segs) {
        if (lastPoint < l) {
            // 当前锚点不覆盖该段——放新锚点
            lastPoint = r;   // 放在右端以覆盖尽量多的后续区间
            count++;
        }
    }

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

与活动选择的联系： 区间刺穿和最多不重叠区间是对偶问题：最少刺穿点数 = 最多不重叠区间数（区间调度的 König 定理）。两者都按右端点排序，代码结构几乎相同。