void insertionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i];   // 要插入的元素
        int j = i - 1;
        // 将大于 key 的元素向右移动一位
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;  // 把 key 放到正确位置
    }
}

void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> tmp(a.begin() + lo, a.begin() + hi + 1);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (tmp[i - lo] <= tmp[j - lo]) {
            a[k++] = tmp[i - lo];  // 左半部分更小，优先放入以保持稳定性
            i++;
        } else {
            a[k++] = tmp[j - lo];
            j++;
        }
    }
    while (i <= mid) { a[k++] = tmp[i - lo]; i++; }
    while (j <= hi)  { a[k++] = tmp[j - lo]; j++; }
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

// 对 arr[lo..hi] 用最后一个元素作枢轴进行分区。
// 返回枢轴的最终下标。
int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];   // 选最后一个元素为枢轴
    int i = lo - 1;        // i 指向「≤ 枢轴」区域的末尾

    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);  // 把 arr[j] 纳入 ≤ 枢轴区域
        }
    }
    swap(arr[i + 1], arr[hi]);  // 把枢轴放到最终位置
    return i + 1;               // 返回枢轴的下标
}

void quickSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;           // 基础情况：子数组长度 ≤ 1
    int p = partition(arr, lo, hi); // p 是枢轴的最终位置
    quickSort(arr, lo, p - 1);      // 排序左子数组
    quickSort(arr, p + 1, hi);      // 排序右子数组
}

// 计数排序（稳定，O(N+W)）
// 要求：所有元素在 [0, W) 范围内
void countingSort(vector<int>& a, int W) {
    int n = a.size();
    vector<int> cnt(W, 0), out(n);

    // 第一步：统计每个值的出现次数
    for (int x : a) cnt[x]++;

    // 第二步：变为前缀和（cnt[i] = 最终 <= i 的元素个数）
    for (int i = 1; i < W; i++) cnt[i] += cnt[i-1];

    // 第三步：从后向前放置（保证稳定性！）
    for (int i = n - 1; i >= 0; i--) {
        out[--cnt[a[i]]] = a[i];
    }
    a = out;
}

// 对键范围已知的使用示例：
// countingSort(arr, 100);  // 所有元素在 [0, 99]

// 基数排序（以 10 为基数的十进制版本）
// O(N * d)，d 为最大数的十进制位数
void radixSort(vector<int>& a) {
    int maxVal = *max_element(a.begin(), a.end());
    int n = a.size();

    // 从最低位（个位）到最高位逐位排序
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        vector<int> cnt(10, 0), out(n);

        // 统计当前位的频率
        for (int i = 0; i < n; i++)
            cnt[(a[i] / exp) % 10]++;

        // 前缀和
        for (int i = 1; i < 10; i++)
            cnt[i] += cnt[i-1];

        // 从后向前放置（稳定性保证）
        for (int i = n-1; i >= 0; i--) {
            int digit = (a[i] / exp) % 10;
            out[--cnt[digit]] = a[i];
        }
        a = out;
    }
}

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

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

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

    // 升序排序
    sort(v.begin(), v.end());

    // 降序排序
    sort(v.begin(), v.end(), greater<int>());

    // 只排序向量的一部分（下标 2 到 5，含）
    sort(v.begin() + 2, v.begin() + 6);

    for (int x : v) cout << x << " ";
    cout << "\n";

    return 0;
}

struct Cow {
    string name;
    int weight;
    int height;
};

// 按体重升序；体重相同时按身高降序
bool cmpCow(const Cow &a, const Cow &b) {
    if (a.weight != b.weight) return a.weight < b.weight;  // 较轻的优先
    return a.height > b.height;                             // 打平：较高的优先
}

int main() {
    vector<Cow> cows = {{"Bessie", 500, 140}, {"Elsie", 480, 135}, {"Moo", 500, 138}};

    sort(cows.begin(), cows.end(), cmpCow);

    for (auto &c : cows) {
        cout << c.name << " " << c.weight << " " << c.height << "\n";
    }
    // 输出：
    // Elsie 480 135
    // Bessie 500 140
    // Moo 500 138
    return 0;
}

// 二分查找 — O(log N)
#include <bits/stdc++.h>
using namespace std;

// 在有序 arr 中返回 target 的下标，未找到返回 -1
int binarySearch(const vector<int> &arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // ← 关键行：避免溢出（不要用 (lo+hi)/2）

        if (arr[mid] == target) {
            return mid;         // 找到！
        } else if (arr[mid] < target) {
            lo = mid + 1;       // 目标在右半部分
        } else {
            hi = mid - 1;       // 目标在左半部分
        }
    }

    return -1;  // 未找到
}

int main() {
    vector<int> v = {1, 3, 5, 7, 9, 11, 13, 15};
    cout << binarySearch(v, 7) << "\n";   // 3（下标）
    cout << binarySearch(v, 6) << "\n";   // -1（未找到）
    return 0;
}

// STL 二分操作 — 全部 O(log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};

    // lower_bound：第一个 >= target 的迭代器
    auto lb = lower_bound(v.begin(), v.end(), 3);
    cout << *lb << "\n";                    // 3（第一个 3）
    cout << lb - v.begin() << "\n";         // 1（下标）

    // upper_bound：第一个 > target 的迭代器
    auto ub = upper_bound(v.begin(), v.end(), 3);
    cout << *ub << "\n";                    // 5（所有 3 后面的第一个元素）
    cout << ub - v.begin() << "\n";         // 3（下标）

    // 统计出现次数：upper_bound - lower_bound
    int count_of_3 = upper_bound(v.begin(), v.end(), 3)
                   - lower_bound(v.begin(), v.end(), 3);
    cout << count_of_3 << "\n";   // 2

    // 检查是否存在
    bool exists = binary_search(v.begin(), v.end(), 7);
    cout << exists << "\n";  // 1

    // 找 <= target 的最大值（向下取整）
    auto it = upper_bound(v.begin(), v.end(), 6);
    if (it != v.begin()) {
        --it;
        cout << *it << "\n";  // 5（<= 6 的最大值）
    }

    return 0;
}

// 二分答案 — O(N log N log(最大距离))
#include <bits/stdc++.h>
using namespace std;

int n, c;
vector<int> stalls;

// 能否放置 c 头奶牛使任意两头间距 >= minDist？
bool canPlace(int minDist) {
    int placed = 1;           // 第一头放在马厩 0
    int lastPos = stalls[0];  // 最后放置的奶牛的位置

    for (int i = 1; i < n; i++) {
        if (stalls[i] - lastPos >= minDist) {  // 这个马厩足够远
            placed++;
            lastPos = stalls[i];
        }
    }
    return placed >= c;  // 放了 c 头奶牛吗？
}

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

    cin >> n >> c;
    stalls.resize(n);
    for (int &x : stalls) cin >> x;
    sort(stalls.begin(), stalls.end());  // 必须先排序！

    // 二分答案：最大可能的最小距离是多少？
    int lo = 1, hi = stalls.back() - stalls.front();
    int answer = 0;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(mid)) {
            answer = mid;    // mid 可行，尝试更大的
            lo = mid + 1;
        } else {
            hi = mid - 1;    // mid 不可行，尝试更小的
        }
    }

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

排序后：[1, 2, 4, 8, 9]
lo=1, hi=8

mid=4：canPlace(4)？
  在 1 放奶牛。下一个 ≥ 1+4=5 的：8，放在 8。
  下一个 ≥ 8+4=12：没有。总共放了 2 头 < 3。返回 false。
  → hi = 3

mid=2：canPlace(2)？
  在 1 放。下一个 ≥ 3：4，放在 4。
  下一个 ≥ 6：8，放在 8。总共 3 头 ≥ 3。返回 true。
  → answer=2, lo=3

mid=3：canPlace(3)？
  在 1 放。下一个 ≥ 4：4，放在 4。
  下一个 ≥ 7：8，放在 8。总共 3 头 ≥ 3。返回 true。
  → answer=3, lo=4

lo=4 > hi=3：结束。答案 = 3

// 代码片段 — 完整程序请参考攻击性奶牛示例
// 能否从绳子中切出 K 段长度 >= len 的？
bool canCut(vector<int> &ropes, long long len, int K) {
    long long count = 0;
    for (int r : ropes) count += r / len;  // 每根绳子能切出的段数
    return count >= K;
}

// 二分：最大化 len 使 canCut(len) 为真
long long lo = 1, hi = *max_element(ropes.begin(), ropes.end());
long long answer = 0;
while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canCut(ropes, mid, K)) {
        answer = mid;
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}

// 通用模板 — 根据题目调整 lo、hi 和 check()
long long lo = 最小可能答案;
long long hi = 最大可能答案;
long long answer = lo;  // 若无有效答案则为 -1

while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) {       // mid 可行
        answer = mid;       // 保存
        lo = mid + 1;       // 尝试更好的（取决于题目是更大还是更小）
    } else {
        hi = mid - 1;       // mid 不可行，降低
    }
}

// 坐标压缩 — O(N log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> A = {100, 500, 200, 100, 700, 200};

    // 第一步：获取有序唯一值
    vector<int> sorted_unique = A;
    sort(sorted_unique.begin(), sorted_unique.end());
    sorted_unique.erase(unique(sorted_unique.begin(), sorted_unique.end()),
                        sorted_unique.end());
    // sorted_unique = {100, 200, 500, 700}

    // 第二步：将每个原始值映射到压缩后的下标
    vector<int> compressed(A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        compressed[i] = lower_bound(sorted_unique.begin(), sorted_unique.end(), A[i])
                        - sorted_unique.begin();
        // 100→0, 200→1, 500→2, 700→3
    }

    for (int x : compressed) cout << x << " ";
    cout << "\n";  // 0 2 1 0 3 1

    return 0;
}

// 检查：能否将任务分配给 K 个工人，使每人工作量 <= T？
bool canFinish(vector<int>& tasks, int K, long long T) {
    int workers = 1;
    long long current = 0;
    for (int t : tasks) {
        if (t > T) return false;  // 单个任务超过 T——不可能
        if (current + t > T) {
            workers++;             // 开始新工人
            current = t;
            if (workers > K) return false;
        } else {
            current += t;
        }
    }
    return true;
}

// 对 T 二分 — 用「lo < hi」模板（最小化答案）
long long lo = *max_element(tasks.begin(), tasks.end());  // T 的最小可能值
long long hi = accumulate(tasks.begin(), tasks.end(), 0LL);  // T 的最大值（1 个工人）

while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canFinish(tasks, K, mid)) hi = mid;  // mid 可行，尝试更小
    else lo = mid + 1;                        // mid 不可行，需要更大
}
cout << lo << "\n";  // 最小可能最大时间（循环结束时 lo == hi）

// 统计 N×M 乘法表中 <= X 的值的个数
long long countLE(long long X, int N, int M) {
    long long count = 0;
    for (int i = 1; i <= N; i++) {
        count += min((long long)M, X / i);
        // 第 i 行的值是 i, 2i, ..., Mi
        // 第 i 行中 <= X 的个数：min(M, floor(X/i))
    }
    return count;
}

// 二分查找第 K 小
long long lo = 1, hi = (long long)N * M;
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (countLE(mid, N, M) >= K) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

// 注意：以下代码假设已定义：#define all(v) (v).begin(), (v).end()
vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};
//               0  1  2  3  4  5  6   7

// ── lower_bound：第一个 >= x 的位置 ──
lower_bound(all(v), 3)  → 下标 1  （第一个 3）
lower_bound(all(v), 4)  → 下标 3  （第一个 >= 4 的元素，即 5）
lower_bound(all(v), 12) → 下标 8  （越界：没有 >= 12 的元素）

// ── upper_bound：第一个 > x 的位置 ──
upper_bound(all(v), 3)  → 下标 3  （所有 3 之后的第一个元素）
upper_bound(all(v), 4)  → 下标 3  （与上同：没有 4）
upper_bound(all(v), 11) → 下标 8  （越界）

// ── 派生操作 ──
// 统计 x 的出现次数：
int cnt = upper_bound(all(v), 3) - lower_bound(all(v), 3);  // cnt = 2

// x 是否存在？
binary_search(all(v), x)  // O(log N)，返回 bool

// <= x 的最大值（向下取整）：
auto it = upper_bound(all(v), x);
if (it != v.begin()) cout << *prev(it);

// >= x 的最小值（向上取整）：
auto it = lower_bound(all(v), x);
if (it != v.end()) cout << *it;

// < x 的最大值（严格向下取整）：
auto it = lower_bound(all(v), x);
if (it != v.begin()) cout << *prev(it);

// < x 的元素个数：
lower_bound(all(v), x) - v.begin()

// <= x 的元素个数：
upper_bound(all(v), x) - v.begin()

// [a, b] 范围内的元素个数：
upper_bound(all(v), b) - lower_bound(all(v), a)

// 自定义谓词二分查找
// 在 [lo, hi] 范围内找第一个 pred(i) 为真的下标
// 假设：pred 单调，即 false...false, true...true

int lo = 0, hi = n - 1, answer = -1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (/* mid 上的某个条件 */) {
        answer = mid;
        hi = mid - 1;  // 找更小的下标
    } else {
        lo = mid + 1;
    }
}

// 示例：第一个 arr[i] - arr[0] >= D 的下标
// （对有序数组，arr[i] - arr[0] 单调非递减，
//  所以这个谓词是单调的：假...假，真...真）
// ⚠️ 关键要求：谓词必须单调，二分查找才有效！
{
    int lo = 0, hi = n - 1, firstFar = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] - arr[0] >= D) {
            firstFar = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
}

// 浮点数二分查找（基于精度）
double lo_f = 0.0, hi_f = 1e9;
for (int iter = 0; iter < 100; iter++) {  // 100 次迭代 → 误差 < 1e-30
    double mid = (lo_f + hi_f) / 2;
    if (check(mid)) hi_f = mid;
    else lo_f = mid;
}
// 答案：lo_f（或 hi_f，两者收敛到相同值）

// 三分查找：求单峰函数 f 在 [lo, hi] 上的极大值
// 前提：f 先增后减（单峰）
// 时间：连续情况 O(log((hi-lo)/eps))，整数情况 O(log N)

// f 必须在调用前声明/定义
double ternarySearch(double lo, double hi) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1;  // 极大值在 [m1, hi] 中
        else hi = m2;                 // 极大值在 [lo, m2] 中
    }
    return (lo + hi) / 2;  // 极大值点（收敛后 lo ≈ hi）
}

// 整数三分查找（f 定义在整数上时）：
int ternarySearchInt(int lo, int hi) {
    // 用 > 2 而非 >= 2：保留至少 3 个候选值再暴力枚举。
    // 范围缩至 2 时，m1 == m2（因为 (hi-lo)/3 == 0），会死循环。
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1 + 1;
        else hi = m2 - 1;
    }
    // 检查剩余候选值 [lo, hi]（最多 3 个元素）
    int best = lo;
    for (int x = lo + 1; x <= hi; x++)
        if (f(x) > f(best)) best = x;
    return best;
}

核心思路： 排序后，相似的值相邻。最近的一对总是排序后的相邻元素。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    int best = INT_MAX;
    for (int i = 1; i < n; i++)
        best = min(best, a[i] - a[i-1]);
    cout << best << "\n";
}

为什么是相邻的？ 若 |a[i] - a[j]| 最小且 j > i+1，则 a[i+1] 在它们之间，所以 a[i+1]-a[i] ≤ a[j]-a[i]，矛盾。

复杂度： O(N log N)。

核心思路： 扫描线。每个开始 +1，每个结束 -1，运行和 = 当前重叠数。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<pair<int,int>> evs;
    for (int i = 0; i < n; i++) {
        int s, e; cin >> s >> e;
        evs.push_back({s, +1});
        evs.push_back({e, -1});
    }
    // 相同时间时先处理结束（delta=-1），「相切」的区间不计为重叠
    sort(evs.begin(), evs.end(),
         [](auto& a, auto& b){ return a.first != b.first ? a.first < b.first : a.second < b.second; });
    int cur = 0, best = 0;
    for (auto& [t, d] : evs) { cur += d; best = max(best, cur); }
    cout << best << "\n";
}

对区间 [(1,4), (2,6), (3,5)] 的追踪：

事件：(1,+1), (2,+1), (3,+1), (4,-1), (5,-1), (6,-1)
扫描：  1       2       3       2       1       0
最大：3（时刻 3 时三个区间同时活跃）

复杂度： O(N log N)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n); for (int& x : a) cin >> x;
    // nth_element 重新排列，使 a[k-1] 到达正确的有序位置
    nth_element(a.begin(), a.begin() + (k-1), a.end());
    cout << a[k-1] << "\n";
}

替代方案：二分答案

int lo = *min_element(a.begin(), a.end());
int hi = *max_element(a.begin(), a.end());
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    int cnt = count_if(a.begin(), a.end(), [&](int x){ return x <= mid; });
    if (cnt >= k) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

复杂度： nth_element 平均 O(N)，最坏 O(N²)；二分答案 O(N log(最大值))。

核心思路： 对答案 D 二分。可行性：贪心地从最左侧马厩开始放奶牛，每次跳到距离 ≥ D 的下一个。

#include <bits/stdc++.h>
using namespace std;
int N, C;
vector<int> p;

bool canPlace(int D) {
    int placed = 1, last = p[0];
    for (int i = 1; i < N; i++) {
        if (p[i] - last >= D) { placed++; last = p[i]; }
        if (placed >= C) return true;
    }
    return false;
}

int main() {
    cin >> N >> C;
    p.resize(N); for (int& x : p) cin >> x;
    sort(p.begin(), p.end());

    int lo = 1, hi = p.back() - p.front(), ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(mid)) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    cout << ans << "\n";
}

复杂度： O(N log N + N log(最大距离))。

核心思路： 对答案 T 二分。可行性：贪心为每个画家填充画板，超过 T 时换下一个画家，若 ≤ K 个画家就够，T 可行。

#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<long long> W;

bool canFinish(long long T) {
    int painters = 1;
    long long cur = 0;
    for (long long w : W) {
        if (w > T) return false;  // 单块画板超出预算
        if (cur + w > T) { painters++; cur = w; }
        else cur += w;
    }
    return painters <= K;
}

int main() {
    cin >> N >> K;
    W.resize(N); for (long long& x : W) cin >> x;
    long long lo = *max_element(W.begin(), W.end());  // 下界：最宽的画板
    long long hi = accumulate(W.begin(), W.end(), 0LL);  // 上界：总宽度
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canFinish(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
}

复杂度： O(N log(总宽度))。

排序陷阱：

• ❌ 比较器用 > 代替 <（排序需要严格弱序）
• ❌ 比较器返回 a <= b——违反严格弱序，可能导致未定义行为
• ❌ 比较器有副作用或随机性——必须是确定性的

二分查找陷阱：

• ❌ mid = (lo + hi) / 2——lo+hi 很大时溢出，用 lo + (hi - lo) / 2
• ❌ 死循环：未找到目标时 lo = mid（而不是 mid+1）
• ❌ 「第一个/最后一个位置」变体中的边界错误——先画出不变量
• ❌ 浮点数二分：用精度终止条件 while (hi - lo > 1e-9)

二分答案陷阱：

• ❌ 检查函数不单调——二分查找无效！验证：若 D 可行，D-1 也可行吗？
• ❌ 边界太紧（遗漏边界情况）：将 lo 设为最小可能答案，hi 设为明确可行的上界