15 · 回顾三：函数、结构体与排序

sort：把相同数字挤到一起，为 unique 创造条件。

unique：把每段连续重复的第一个留在原地，返回去重后区间的新末尾。

erase：删掉 [新末尾, 原末尾) 这段垃圾，size() 才等于真实答案。

先输出 size，再按下标输出。复杂度 O(n log n + n)，n ≤ 100 瞬间过。

同理可推广：若值域是 10⁹ 而 n 只有 10⁵，排序去重后配合二分就是离散化。

#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];

    sort(a.begin(), a.end());                      // 先让相同元素相邻
    a.erase(unique(a.begin(), a.end()), a.end());   // 再去重并真正缩短

    cout << a.size() << "\n";
    int m = (int)a.size();                          // size() 是无符号数，先转 int
    for (int i = 0; i < m; ++i)
        cout << a[i] << (i + 1 == m ? '\n' : ' ');  // 行末只换行，不加空格
    return 0;
}

结构体存 name、y、m、d、id，id 是读入顺序（从 0 开始）。

cmp 四层：年小在前 → 月小在前 → 日小在前 → id 大在前。

前三层用「出生早 = 年龄大」；第四层用「id 大 = 输入靠后」。

id 互不相同，所以第四层保证任意两人一定分出胜负，严格弱序成立。

sort 后按顺序输出姓名。交换的是整个结构体，姓名跟着生日一起走，不会错配。

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

struct Node {
    string name;
    int y, m, d, id;     // id：读入顺序，从 0 开始
};

bool cmp(const Node &a, const Node &b) {
    if (a.y != b.y) return a.y < b.y;   // 出生早的年龄大
    if (a.m != b.m) return a.m < b.m;
    if (a.d != b.d) return a.d < b.d;
    return a.id > b.id;                 // 生日相同：输入靠后的先输出
}

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

    int n;
    cin >> n;
    vector<Node> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i].name >> v[i].y >> v[i].m >> v[i].d;
        v[i].id = i;
    }

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

    for (const auto &x : v) cout << x.name << "\n";
    return 0;
}

读入 + 排序：cmp 两个关键字，成绩降序、报名号升序。

need = ⌊1.5m⌋，再用 min(n, need) 夹一下——m 接近 n 时 1.5m 会超过总人数。

分数线 line = v[need-1].sc：下标从 0 开始，第 need 名就是 v[need-1]。

实际人数 cnt = 从前往后数第一个「成绩 < line」的位置，这自动把并列的人全算进来。

先输出 line 与 cnt，再输出前 cnt 个人的报名号与成绩。

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

struct P {
    int id, sc;
};

bool cmp(const P &a, const P &b) {
    if (a.sc != b.sc) return a.sc > b.sc;   // 成绩高的在前
    return a.id < b.id;                     // 同分报名号小的在前
}

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

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

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

    int need = m * 3 / 2;            // ⌊1.5m⌋，整数运算没有精度问题
    if (need > n) need = n;          // 1.5m 可能超过总人数
    int line = v[need - 1].sc;       // 第 need 名的分数就是分数线

    int cnt = 0;
    while (cnt < n && v[cnt].sc >= line) ++cnt;   // 并列的全进，重新数

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

nth_element(a, a+k, a+n) 执行完后 a[k] 就是第 k 小（0 起），平均 O(n)。

它的原理是快速选择：按基准把区间分成两半，只继续处理包含 k 的那一半，所以是 O(n) 而不是 O(n log n)。

左侧元素都不大于 a[k]，右侧都不小于 a[k]，但两侧都没有排好序。

5×10⁶ 个 int 约 20MB，必须放全局数组：栈空间只有几 MB，放 main 里直接栈溢出 RE。

手写快读逐字符解析，比 cin 快 2~3 倍，也顺手解决「数据跨行」的问题。

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

const int MAXN = 5000000;
int a[MAXN + 5];          // 全局数组：静态区，不受栈大小限制

int readInt() {           // 手写快读，返回一个 int
    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 = readInt(), k = readInt();
    for (int i = 0; i < n; ++i) a[i] = readInt();

    nth_element(a, a + k, a + n);     // 执行后 a[k] 就是第 k 小
    printf("%d\n", a[k]);
    return 0;
}

偶数位回文数一定能被 11 整除：以 abba 为例，1001a + 110b = 11(91a + 10b)。

所以除 11 本身以外，偶数位回文数全是合数。答案都落在 1~7 位数里。

把 b 截断到 9999999，枚举量从 10⁸ 降到 10⁷。

枚举 i ∈ [a, b]：先判回文（几次除法，极快），是回文再判质数（试除到 √i）。

只有回文才做质数判定，实际质数判定约 1.1 万次，总耗时约 0.1 秒。

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

bool isPrime(int x) {
    if (x < 2) return false;                        // 0、1 不是质数
    for (int i = 2; (long long)i * i <= x; ++i)     // 只试到 √x
        if (x % i == 0) return false;
    return true;
}

bool isPal(int x) {
    int t = x, r = 0;
    while (t > 0) { r = r * 10 + t % 10; t /= 10; } // 把 x 倒过来
    return r == x;                                  // 用临时变量，不改原数
}

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

    int a, b;
    cin >> a >> b;
    if (b > 9999999) b = 9999999;   // 8 位及以上回文数都是 11 的倍数

    for (int i = a; i <= b; ++i)
        if (isPal(i) && isPrime(i)) cout << i << "\n";
    return 0;
}