算法模板库 常用函数 全解析

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

struct Stu {
    int id;      // 学号
    int total;   // 总分
    int cpp;     // C++ 单科
};

// 比较器写法一：普通函数
bool cmp1(const Stu& a, const Stu& b) {
    if (a.total != b.total) return a.total > b.total;   // 总分高的在前
    return a.id < b.id;                              // 总分相同学号小的在前
}

void show(vector<Stu>& v, string name) {
    cout << name << " : ";
    for (auto& s : v) cout << "(" << s.id << "," << s.total << ") ";
    cout << "\n";
}

int main() {
    vector<Stu> v = {{3,280,95}, {1,300,80}, {2,280,99}, {4,250,70}};

    // ① 基础排序（默认升序，作用于基本类型）
    vector<int> a = {5, 3, 8, 1, 2};
    sort(a.begin(), a.end());
    cout << "升序："; for (int x : a) cout << x << " ";
    cout << "\n";

    sort(a.begin(), a.end(), greater<int>());   // 降序
    cout << "降序："; for (int x : a) cout << x << " ";
    cout << "\n";

    // ② 结构体多关键字排序
    vector<Stu> v1 = v;
    sort(v1.begin(), v1.end(), cmp1);
    show(v1, "sort 多关键字");

    // ③ lambda 比较器（C++11，最紧凑）
    vector<Stu> v2 = v;
    sort(v2.begin(), v2.end(), [](const Stu& x, const Stu& y) {
        return x.cpp != y.cpp ? x.cpp > y.cpp : x.id < y.id;
    });
    show(v2, "lambda 按 C++ 单科");

    // ④ 稳定排序演示：只按 total 排序，保留原来的相对顺序
    vector<Stu> v3 = v;
    stable_sort(v3.begin(), v3.end(),
                [](const Stu& x, const Stu& y) { return x.total > y.total; });
    show(v3, "stable_sort 只按总分");

    // 对比：用 sort 排序同样规则，相等元素的顺序「不确定」
    vector<Stu> v4 = v;
    sort(v4.begin(), v4.end(),
         [](const Stu& x, const Stu& y) { return x.total > y.total; });
    show(v4, "sort 只按总分");

    // ⑤ 部分排序：只排前 3 个
    vector<int> b = {9, 5, 7, 1, 3, 8};
    partial_sort(b.begin(), b.begin() + 3, b.end());   // 前 3 个是最小的 3 个且有序
    cout << "partial_sort 前 3 小且有序：";
    for (int i = 0; i < 3; i++) cout << b[i] << " ";
    cout << "\n";
    return 0;
}

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

int main() {
    // ① 两值取最值
    int a = 5, b = 9;
    cout << "min = " << min(a, b) << ", max = " << max(a, b) << "\n";

    // ② 一次取两个（C++11）：避免「% 取模」这种老掉牙的写法
    auto p = minmax(7, 2);
    cout << "minmax(7,2) = (" << p.first << ", " << p.second << ")\n";

    // ③ 多值取最值（initializer_list 版本，C++11）
    cout << "min({3,8,1,9,4}) = " << min({3, 8, 1, 9, 4}) << "\n";   // 1
    cout << "max({3,8,1,9,4}) = " << max({3, 8, 1, 9, 4}) << "\n";   // 9

    // ④ clamp（C++17）：把值限制在 [lo, hi] 区间内
    cout << "clamp(15, 0, 10) = " << clamp(15, 0, 10) << "\n";   // 10
    cout << "clamp(-3, 0, 10) = " << clamp(-3, 0, 10) << "\n";   // 0

    // ⑤ 容器/数组求最值：返回「迭代器」，不是值！
    vector<int> v = {3, 9, 1, 7};
    auto itMax = max_element(v.begin(), v.end());
    auto itMin = min_element(v.begin(), v.end());
    cout << "max = " << *itMax << "，位置下标 = " << (itMax - v.begin()) << "\n";
    cout << "min = " << *itMin << "，位置下标 = " << (itMin - v.begin()) << "\n";

    // ⑥ swap：交换两个同类型对象，O(1)
    swap(a, b);                       // a=9, b=5
    cout << "swap 后 a=" << a << ", b=" << b << "\n";

    vector<int> x = {1,2}, y = {3,4,5};
    x.swap(y);                        // 交换两个容器的全部内容，O(1)（只换指针）
    cout << "交换后 x 的 size = " << x.size() << "\n";   // 3
    return 0;
}

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

void show(vector<int>& v, string name) {
    cout << name << " : [";
    for (int i = 0; i < (int)v.size(); i++) cout << v[i] << (i + 1 < (int)v.size() ? ", " : "");
    cout << "]  size=" << v.size() << "\n";
}

int main() {
    // ① reverse：原地翻转 O(n)
    vector<int> v = {1, 2, 3, 4, 5};
    reverse(v.begin(), v.end());
    show(v, "reverse 后");
    reverse(v.begin(), v.begin() + 2);        // 只翻转前两个
    show(v, "只翻前两个");

    // ② unique：把相邻重复项挪到后面，返回「新末尾」
    vector<int> w = {1, 1, 2, 3, 3, 3, 5};
    auto newEnd = unique(w.begin(), w.end());
    cout << "unique 之后 size 仍是 " << w.size()
         << "，新末尾下标 = " << (newEnd - w.begin()) << "\n";
    show(w, "unique 后（未 erase）");

    // ★ 标准去重套路：先 sort，再 unique + erase
    vector<int> u = {3, 1, 3, 2, 1, 3};
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());
    show(u, "去重后");

    // ③ rotate：循环左移（把 first 搬到 middle 位置）
    vector<int> r = {1, 2, 3, 4, 5};
    rotate(r.begin(), r.begin() + 2, r.end());   // 前两个搬到末尾
    show(r, "rotate 左移 2 位");

    // ④ fill：把区间全部赋值（比 for 循环更清晰）
    vector<int> f(6);
    fill(f.begin(), f.end(), 7);
    show(f, "fill 7");

    // ⑤ iota：递增填充（«numeric»）
    vector<int> g(6);
    iota(g.begin(), g.end(), 1);          // 填 1,2,3,4,5,6
    show(g, "iota 从 1 开始");

    // ⑥ count：统计某个值出现次数（«algorithm»）
    vector<int> c = {1, 2, 2, 3, 2};
    cout << "count(2) = " << count(c.begin(), c.end(), 2) << "\n";   // 3

    // ⑦ count_if：统计满足条件的元素个数
    int odd = count_if(c.begin(), c.end(), [](int x) { return x % 2 == 1; });
    cout << "奇数个数 = " << odd << "\n";    // 2

    // ⑧ accumulate：求和（«numeric»），第三参数是「初值」
    long long sum = accumulate(c.begin(), c.end(), 0LL);
    cout << "总和 = " << sum << "\n";         // 10
    long long prod = accumulate(c.begin(), c.end(), 1LL, multiplies<long long>());
    cout << "连乘 = " << prod << "\n";        // 24 = 1*2*2*3*2
    return 0;
}

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

int main() {
    // 下标: 0 1 2 3 4 5 6  7  8
    int a[] = {1, 3, 3, 3, 5, 7, 9, 11, 11};
    int n = 9;

    for (int q : {0, 3, 4, 11, 12}) {
        int lb = lower_bound(a, a + n, q) - a;   // 第一个 >= q 的下标
        int ub = upper_bound(a, a + n, q) - a;   // 第一个 >  q 的下标
        bool has = binary_search(a, a + n, q);
        cout << "查询 " << setw(2) << q
             << " → lower=" << lb
             << ", upper=" << ub
             << ", 出现次数=" << ub - lb
             << ", 是否存在=" << (has ? "Y" : "N") << "\n";
    }

    // 前驱：≤ 4 的最大值
    auto it = upper_bound(a, a + n, 4);
    if (it != a) { --it; cout << "≤4 的最大值 = " << *it << "\n"; }   // 3

    // 后继：≥ 4 的最小值
    auto it2 = lower_bound(a, a + n, 4);
    if (it2 != a + n) cout << "≥4 的最小值 = " << *it2 << "\n";   // 5

    // 在 vector 上使用
    vector<long long> v = {10, 20, 20, 30, 40};
    int pos = lower_bound(v.begin(), v.end(), 20) - v.begin();
    cout << "v 中 20 首次出现于下标 " << pos << "\n";                   // 1

    // 降序数组必须传 greater<int>()
    vector<int> d = {40, 30, 20, 10};
    auto it3 = lower_bound(d.begin(), d.end(), 25, greater<int>());
    cout << "降序数组中第一个 ≤25 的值 = " << *it3 << "\n";               // 20
    return 0;
}

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

int a[5];
long long b[5];

int main() {
    // —— memset 能做的：填 0 ——
    memset(a, 0, sizeof(a));
    cout << "memset 0  → "; for (int x : a) cout << x << " "; cout << "\n";

    // —— memset 能做的：填 -1 ——
    memset(a, -1, sizeof(a));
    cout << "memset -1 → "; for (int x : a) cout << x << " "; cout << "\n";

    // —— memset 能做的：填 0x3f（当无穷大用）——
    memset(a, 0x3f, sizeof(a));
    cout << "memset 0x3f → "; for (int x : a) cout << x << " "; cout << "\n";

    // —— memset 做不到的：填 1 ——
    memset(a, 1, sizeof(a));
    cout << "memset 1  → "; for (int x : a) cout << x << " "; cout << "\n";   // 全是 16843009

    // —— 正确做法：fill ——
    fill(a, a + 5, 1);
    cout << "fill 1    → "; for (int x : a) cout << x << " "; cout << "\n";

    // —— long long 的大数用 0x3f 要注意！——
    // memset 到 long long 上会得到 0x3f3f3f3f3f3f3f3f ≈ 4.5×10^18，太大且容易溢出
    memset(b, 0x3f, sizeof(b));
    cout << "long long 上的 memset 0x3f = " << b[0] << "\n";
    // 推荐：long long 的「无穷大」直接写常数
    const long long INF = 0x3f3f3f3f3f3f3f3fLL;
    fill(b, b + 5, INF);
    cout << "fill INF   = " << b[0] << "\n";

    // ============ GCC 内建函数 ============
    unsigned int x = 0b10110100;   // 二进制字面量（C++14）
    cout << "x = " << bitset<8>(x) << "\n";
    cout << "__builtin_popcount(x) = " << __builtin_popcount(x) << "\n";   // 1 的个数 = 4
    cout << "__builtin_ctz(x)      = " << __builtin_ctz(x) << "\n";      // 末尾 0 的个数 = 2
    cout << "__builtin_clz(x)      = " << __builtin_clz(x) << "\n";      // 32 位下的前导 0 = 24

    // 高精度版本：参数加 ll 后缀，用于 long long
    long long y = 0x0000000000000000LL;
    cout << "popcountll(y) = " << __builtin_popcountll(y) << "\n";

    // 常用推论
    int v = 12;                       // 1100
    cout << "lowbit(12) = " << (v & -v) << "\n";                          // 4
    cout << "最高位编号 = " << (31 - __builtin_clz(v)) << "\n";         // 3（即 2^3=8）
    cout << "是否 2 的幂 = " << ((v & (v - 1)) == 0 ? "Y" : "N") << "\n";  // N
    return 0;
}

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

int main() {
    vector<int> a = {7, 3, 9, 1, 5, 8, 2, 6, 4};
    int n = a.size();

    // 求第 3 小（下标 2）
    vector<int> b = a;
    nth_element(b.begin(), b.begin() + 2, b.end());
    cout << "第 3 小 = " << b[2] << "\n";          // 3
    cout << "nth_element 后整个数组：";
    for (int x : b) cout << x << " ";
    cout << "\n";   // 左半 ≤ b[2]，右半 ≥ b[2]，但两边内部无序

    // 求第 2 大：用 greater 反向比较
    vector<int> c = a;
    nth_element(c.begin(), c.begin() + 1, c.end(), greater<int>());
    cout << "第 2 大 = " << c[1] << "\n";          // 8

    // 求中位数（n 为奇数时）
    vector<int> d = a;
    nth_element(d.begin(), d.begin() + n / 2, d.end());
    cout << "中位数 = " << d[n / 2] << "\n";         // 5

    // 顺便取出「前 k 小」（前 k 个位置就是最小的 k 个，但内部无序）
    vector<int> e = a;
    nth_element(e.begin(), e.begin() + 4, e.end());
    cout << "前 5 小（未排序）：";
    for (int i = 0; i < 5; i++) cout << e[i] << " ";
    cout << "\n";
    sort(e.begin(), e.begin() + 5);                 // 再排一下前 5 个就得到有序的前 k 小
    cout << "前 5 小（已排序）：";
    for (int i = 0; i < 5; i++) cout << e[i] << " ";
    cout << "\n";
    return 0;
}

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

int main() {
    // ① 枚举 1..4 的全部排列（必须从最小排列开始！）
    vector<int> a = {1, 2, 3, 4};
    int cnt = 0;
    do {
        cout << "[";
        for (int i = 0; i < 4; i++) cout << a[i] << (i < 3 ? "," : "");
        cout << "] ";
        cnt++;
    } while (next_permutation(a.begin(), a.end()));
    cout << "\n共 " << cnt << " 个排列（4! = 24）\n";

    // ② 带剪枝：只枚举「1 在 2 前面」的排列（减少一半搜索量）
    vector<int> b = {1, 2, 3, 4};
    vector<vector<int>> good;
    do {
        int p1 = 0, p2 = 0;
        for (int i = 0; i < 4; i++) { if (b[i] == 1) p1 = i; if (b[i] == 2) p2 = i; }
        if (p1 < p2) good.push_back(b);
    } while (next_permutation(b.begin(), b.end()));
    cout << "1 在 2 前面的排列数 = " << good.size() << "（24/2 = 12）\n";

    // ③ 字符串也能全排列
    string s = "abc";
    cout << "abc 的全排列：";
    sort(s.begin(), s.end());        // 先排成最小排列
    do { cout << s << " "; } while (next_permutation(s.begin(), s.end()));
    cout << "\n";

    // ④ 求「指定排列的下一个」（P1088 火星人的做法）
    vector<int> c = {1, 3, 2};
    next_permutation(c.begin(), c.end());
    cout << "132 的下一个排列 = ";
    for (int x : c) cout << x;
    cout << "\n";   // 213

    // ⑤ prev_permutation：反向，求上一个排列
    vector<int> d = {2, 1, 3};
    prev_permutation(d.begin(), d.end());
    cout << "213 的上一个排列 = ";
    for (int x : d) cout << x;
    cout << "\n";   // 132
    return 0;
}

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

struct Stu {
    int id;        // 学号
    int chinese;   // 语文
    int total;     // 三科总分
};

// 比较器：返回 true 表示 a 应该排在 b 前面
bool cmp(const Stu& a, const Stu& 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(0);
    cin.tie(0);

    int n; cin >> n;
    vector<Stu> v(n);
    for (int i = 0; i < n; i++) {
        int c, m, e;
        cin >> c >> m >> e;
        v[i] = {i + 1, c, c + m + e};
    }

    sort(v.begin(), v.end(), cmp);

    int out = min(5, n);          // 可能不足 5 人
    for (int i = 0; i < out; i++)
        cout << v[i].id << " " << v[i].total << "\n";
    return 0;
}

// 把 cmp 删掉，sort 改成：
sort(v.begin(), v.end(), [](const Stu& a, const Stu& 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;
});

// 也可以用 tuple 的字典序比较，一行搞定（推荐熟练后使用）：
// sort(v.begin(), v.end(), [](const Stu& a, const Stu& b) {
//     return tie(b.total, b.chinese, a.id) < tie(a.total, a.chinese, b.id);
// });

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

const int MAXN = 5000005;
int a[MAXN];

// 快读：5×10^6 的数据必须用
int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

int main() {
    int n = read(), k = read();
    for (int i = 0; i < n; i++) a[i] = read();

    // 第 k 小 → 下标 k-1
    nth_element(a, a + k - 1, a + n);
    printf("%d\n", a[k - 1]);
    return 0;
}

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

const int MAXN = 5000005;
int a[MAXN];

// 返回 a[L..R] 中第 k 小（k 从 1 开始计）
int quickSelect(int L, int R, int k) {
    if (L == R) return a[L];

    // 三数取中选枢轴，降低退化概率
    int mid = (L + R) >> 1;
    int p = a[L] + a[R] + a[mid] - max({a[L], a[R], a[mid]}) - min({a[L], a[R], a[mid]});
    int i = L, j = R, pivot = p;
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) { swap(a[i], a[j]); i++; j--; }
    }
    // 划分后：[L, j] ≤ pivot ≤ [i, R]
    if (L + k - 1 <= j) return quickSelect(L, j, k);           // 只递归左边
    if (L + k - 1 >= i) return quickSelect(i, R, k - (i - L));  // 只递归右边
    return pivot;                                           // 答案就是枢轴
}

int main() {
    int n, k; scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    printf("%d\n", quickSelect(0, n - 1, k));
    return 0;
}

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

long long a[100005];
int n, q;

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

    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);                       // ★ 二分的前提：必须有序

    while (q--) {
        long long v; cin >> v;

        // (1) 存在性
        bool has = binary_search(a, a + n, v);

        // (2) 首次出现的下标（存在时）
        int first = -1;
        int lb = lower_bound(a, a + n, v) - a;      // 第一个 >= v
        if (lb < n && a[lb] == v) first = lb;       // ★ 必须验证 a[lb] == v

        // (3) 出现次数
        int ub = upper_bound(a, a + n, v) - a;      // 第一个 > v
        int cnt = ub - lb;                          // v 不存在时为 0，天然正确

        // (4) 前驱与后继
        long long pre = LLONG_MIN, suf = LLONG_MAX;
        auto it = upper_bound(a, a + n, v);
        if (it != a) { --it; pre = *it; }
        auto it2 = lower_bound(a, a + n, v);
        if (it2 != a + n) suf = *it2;

        cout << "v=" << v
             << " 存在=" << (has ? "Y" : "N")
             << " 首次下标=" << first
             << " 次数=" << cnt
             << " 前驱=" << (pre == LLONG_MIN ? "无" : to_string(pre))
             << " 后继=" << (suf == LLONG_MAX ? "无" : to_string(suf)) << "\n";
    }
    return 0;
}

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

int main() {
    vector<int> p = {1, 2, 3, 4, 5, 6, 7, 8, 9};   // 从最小排列开始
    int solutions = 0;

    do {
        // 前 3 位拼成第一个加数
        int x = p[0] * 100 + p[1] * 10 + p[2];
        int y = p[3] * 100 + p[4] * 10 + p[5];
        int z = p[6] * 100 + p[7] * 10 + p[8];
        if (x + y == z) {
            cout << x << " + " << y << " = " << z << "\n";
            solutions++;
        }
    } while (next_permutation(p.begin(), p.end()));

    cout << "共找到 " << solutions << " 组有序解（加数互换算两组）\n";
    return 0;
}

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

struct P {
    int id;      // 报名号
    int score;   // 笔试成绩
};

bool cmp(const P& a, const P& b) {
    if (a.score != b.score) return a.score > b.score;  // 成绩降序
    return a.id < b.id;                              // 成绩相同报名号升序
}

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

    int n, m; cin >> n >> m;
    vector<P> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].id >> v[i].score;

    sort(v.begin(), v.end(), cmp);

    int rank = m * 3 / 2;            // m × 150%，整数除法自动向下取整
    int line = v[rank - 1].score;      // 第 rank 名的成绩就是分数线（下标 rank-1）

    int cnt = 0;
    while (cnt < n && v[cnt].score >= line) cnt++;   // 并列会让人数超过 rank

    cout << line << " " << cnt << "\n";
    for (int i = 0; i < cnt; i++)
        cout << v[i].id << " " << v[i].score << "\n";
    return 0;
}

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

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

    int n; long long c;
    cin >> n >> c;

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

    sort(a.begin(), a.end());        // ★ 二分的前提

    long long ans = 0;               // 答案可能很大，用 long long
    for (int j = 0; j < n; j++) {
        long long target = a[j] + c;                     // 找 A[i] = A[j] + C
        auto lb = lower_bound(a.begin(), a.end(), target);  // 第一个 ≥ target
        auto ub = upper_bound(a.begin(), a.end(), target);  // 第一个 > target
        ans += ub - lb;                                       // target 的出现次数
    }
    cout << ans << "\n";
    return 0;
}

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

int main() {
    ios::sync_with_stdio(0);
    int n; long long c; cin >> n >> c;
    map<long long, long long> cnt;
    for (int i = 0; i < n; i++) { long long x; cin >> x; cnt[x]++; }
    long long ans = 0;
    for (auto& kv : cnt) {
        auto it = cnt.find(kv.first + c);     // ★ 用 find，别用 []
        if (it != cnt.end()) ans += kv.second * it->second;
    }
    cout << ans << "\n";
    return 0;
}

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

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

    int n, k; cin >> n >> k;
    vector<long long> a(n);
    map<long long, int> freq;
    for (int i = 0; i < n; i++) { cin >> a[i]; freq[a[i]]++; }

    // (1) 去重 + 升序
    vector<long long> u = a;
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());
    for (int i = 0; i < (int)u.size(); i++)
        cout << u[i] << (i + 1 < (int)u.size() ? ' ' : '\n');

    // (2) 第 k 小：去重后有序，直接下标访问
    cout << u[k - 1] << "\n";

    // (3) 中位数
    int m = u.size();
    double med;
    if (m % 2 == 1) med = u[m / 2];
    else med = (u[m / 2 - 1] + u[m / 2]) / 2.0;   // 2.0 保证浮点除法
    cout << fixed << setprecision(1) << med << "\n";

    // (4) 恰好出现 2 次的值个数
    cout << count_if(freq.begin(), freq.end(),
                     [](const pair<const long long, int>& kv) { return kv.second == 2; })
         << "\n";
    return 0;
}

#include <bits/stdc++.h>      // 包含 algorithm / numeric / 全部容器
using namespace std;

struct Node { int score, id; };

// ============ 一、排序与最值 ============
void sortDemo(vector<int>& v, vector<Node>& w) {
    sort(v.begin(), v.end());                                  // 升序
    sort(v.begin(), v.end(), greater<int>());                 // 降序
    sort(w.begin(), w.end(), [](const Node& a, const Node& b) { // 多关键字
        if (a.score != b.score) return a.score > b.score;
        return a.id < b.id;                                    // 最后必须用严格小于
    });
    stable_sort(w.begin(), w.end(),                          // 稳定排序
                [](const Node& a, const Node& b) { return a.score > b.score; });
    partial_sort(v.begin(), v.begin() + 3, v.end());          // 前 3 小且有序

    int mx = *max_element(v.begin(), v.end());
    int mxi = max_element(v.begin(), v.end()) - v.begin();
    int mn = min({3, 1, 4});                                  // 多值取最小
    auto p = minmax(5, 2);                                   // p.first 最小, p.second 最大
}

// ============ 二、区间操作 ============
void rangeDemo(vector<int>& v) {
    reverse(v.begin(), v.end());                               // 翻转
    rotate(v.begin(), v.begin() + 2, v.end());               // 循环左移
    fill(v.begin(), v.end(), 7);                               // 全部填 7
    iota(v.begin(), v.end(), 1);                              // 依次填 1,2,3,...

    // ★ 去重三件套
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    long long sum = accumulate(v.begin(), v.end(), 0LL);
    int c1 = count(v.begin(), v.end(), 7);
    int c2 = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
}

// ============ 三、二分三兄弟（要求区间有序！）============
void binaryDemo(vector<int>& v, int x) {
    sort(v.begin(), v.end());                                  // 前提
    bool has = binary_search(v.begin(), v.end(), x);
    int lb = lower_bound(v.begin(), v.end(), x) - v.begin();   // 第一个 >= x
    int ub = upper_bound(v.begin(), v.end(), x) - v.begin();   // 第一个 >  x
    int cnt = ub - lb;                                          // x 的出现次数
    bool realHas = (lb < (int)v.size() && v[lb] == x);        // ★ 必须验证

    // 前驱：≤ x 的最大值
    auto it = upper_bound(v.begin(), v.end(), x);
    if (it != v.begin()) { --it; /* *it 就是前驱 */ }
    // 后继：≥ x 的最小值
    auto it2 = lower_bound(v.begin(), v.end(), x);
    // if (it2 != v.end()) { ... }

    // 降序数组要传 greater
    // lower_bound(d.begin(), d.end(), x, greater<int>());
}

// ============ 四、选择与排列 ============
void selectDemo(vector<int>& v, int k) {
    // 第 k 小（期望 O(n)）
    nth_element(v.begin(), v.begin() + k - 1, v.end());
    int kthSmallest = v[k - 1];

    // 第 k 大
    nth_element(v.begin(), v.begin() + k - 1, v.end(), greater<int>());
    int kthLargest = v[k - 1];

    // 全排列枚举（必须从最小排列开始）
    sort(v.begin(), v.end());
    do {
        // 处理当前排列 v
    } while (next_permutation(v.begin(), v.end()));

    // 上一个排列
    // prev_permutation(v.begin(), v.end());
}

// ============ 五、初始化与位运算内建 ============
int g[1005][1005];
void initDemo() {
    memset(g, 0, sizeof(g));              // ✅ 填 0
    memset(g, -1, sizeof(g));             // ✅ 填 -1
    memset(g, 0x3f, sizeof(g));            // ✅ 填「无穷大」0x3f3f3f3f
    // memset(g, 1, sizeof(g));              // ❌ 得到 16843009
    fill(&g[0][0], &g[0][0] + 1005 * 1005, 1);  // ✅ 真正填 1

    unsigned int x = 12345;
    int pc = __builtin_popcount(x);      // 1 的个数
    int tz = __builtin_ctz(x);           // 末尾 0 的个数（lowbit 的指数）
    int lz = __builtin_clz(x);           // 前导 0 的个数
    int hi = 31 - lz;                    // 最高位编号
    int lowb = x & -x;                   // lowbit
    // long long 版本：__builtin_popcountll / ctzll / clzll
}

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

int main() {
    ios::sync_with_stdio(0);
    int n; cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    // ① 拷贝一份用于排序去重
    vector<long long> b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    // ② 把原数组换成 1..m 的排名
    for (int i = 0; i < n; i++)
        a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;

    for (int x : a) cout << x << " ";
    cout << "\n";
    cout << "不同值的个数 = " << b.size() << "\n";
    return 0;
}

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

struct P {
    int id, score, penalty, submit, rank;
};

int main() {
    ios::sync_with_stdio(0);
    int n; cin >> n;
    vector<P> v(n);
    for (int i = 0; i < n; i++) {
        v[i].id = i;
        cin >> v[i].score >> v[i].penalty >> v[i].submit;
    }

    // 用 tuple 的字典序比较：注意「降序」通过取负号实现
    sort(v.begin(), v.end(), [](const P& a, const P& b) {
        return make_tuple(-a.score, a.penalty, a.submit) <
               make_tuple(-b.score, b.penalty, b.submit);
    });

    // 并列名次：与前一个人三项都相同则名次相同
    for (int i = 0; i < n; i++) {
        if (i == 0) v[i].rank = 1;
        else if (v[i].score == v[i-1].score &&
                 v[i].penalty == v[i-1].penalty &&
                 v[i].submit == v[i-1].submit)
            v[i].rank = v[i-1].rank;         // 并列
        else v[i].rank = i + 1;             // 跳过并列占用的名次
    }

    for (auto& p : v) cout << "选手" << p.id << " 第 " << p.rank << " 名\n";
    return 0;
}

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

int n, k;
long long L[100005];

// 判断每段长度为 len 时，能否切出至少 k 段
bool check(long long len) {
    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += L[i] / len;
        if (cnt >= k) return true;      // 提前剪枝
    }
    return cnt >= k;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> k;
    long long hi = 0;
    for (int i = 0; i < n; i++) { cin >> L[i]; hi = max(hi, L[i]); }

    long long lo = 1, ans = 0;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;   // 防溢出写法
        if (check(mid)) { ans = mid; lo = mid + 1; }   // 可行 → 尝试更长
        else hi = mid - 1;
    }
    cout << ans << "\n";
    return 0;
}