Day 12 · 排序：sort 与它的朋友们

题意：明明生成了 N 个 1 到 1000 之间的随机整数，其中重复的只保留一个。 要求先输出去重后有多少个不同的数（M），再把这些数从小到大排好序输出。

思路

题目要求的是「去重 + 排序」两件事，而这两件事有天然的联系：排完序之后，相同的数一定挨在一起， 于是「去重」就退化成了「删掉相邻的重复项」。

两种写法：

1. 通用写法：sort 排序 → unique 去重相邻重复项 → 得到新的长度 m。
2. 桶写法：开一个 vis[1005]，读到哪个数就给哪个桶插旗； 最后从 1 扫到 1000，有旗子的数字天然就是升序且不重复的。

10
20 40 32 67 40 20 89 300 400 15

8
15 20 32 40 67 89 300 400

10 个数里 20 和 40 各出现了两次，去重后剩 8 个。

完整代码（写法一：sort + unique）

#include <iostream>
#include <algorithm>
using namespace std;

int a[105];

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

    sort(a, a + n);                         // ① 排序

    // ② 去重：unique 把不重复的元素挪到前面，返回「新区间末尾」的指针
    int m = unique(a, a + n) - a;

    cout << m << endl;                      // ③ 先输出去重后的个数
    for(int i = 0; i < m; i++){
        if(i) cout << " ";                  // 数字之间一个空格，末尾不多打
        cout << a[i];
    }
    cout << endl;
    return 0;
}

完整代码（写法二：标记桶）

#include <iostream>
using namespace std;

int a[105];
bool vis[1005];     // 桶：vis[v] 标记数字 v 出现过

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        vis[a[i]] = true;       // 出现过的数，在它自己的桶里插一面旗
    }

    int m = 0;
    for(int v = 1; v <= 1000; v++){
        if(vis[v]) m++;         // 从小到大扫桶，顺便数出有多少个不同的数
    }

    cout << m << endl;
    int printed = 0;
    for(int v = 1; v <= 1000; v++){
        if(vis[v]){
            if(printed) cout << " ";
            cout << v;
            printed++;
        }
    }
    cout << endl;
    return 0;
}

8
15 20 32 40 67 89 300 400

易错点

• 先 unique 再 sort：unique 只删相邻重复项，没排序时重复的数不挨着，一个也删不掉。顺序不能反。
• 忘了输出 M：题目要输出两行，第一行是不同数的个数，很容易只输出排序结果。
• 输出末尾多打空格：洛谷一般能容忍行末空格，但用 if(i) cout << " "; 的写法更规范。
• 桶写法里桶的大小要开到 1000 以上（数值上限 1000，所以 vis[1005]）， 开成 vis[1000] 在读入 1000 时会越界。

题意：给出 n 个正整数，把它们首尾相接拼成一排，组成一个最大的整数，输出这个整数。

思路：这题的关键是「两个数谁该排前面」

先说一个错误但非常诱人的想法：把数字当字符串，按字典序从大到小排，然后拼起来。

它对样例居然是对的！但它是错的。看这个反例：

（上面两组我都真的编译运行验证过：我的正确程序输出 331 和 991； 专门写了一个「字典序降序」的错误版本，输出的正是 313 和 919。）

如果 a + b > b + a，那么 a 应该排在 b 前面

为什么这样比是对的

三个理由，说服你自己：

1. a+b 和 b+a 的长度一定相同（都是「a 的长度 + b 的长度」）。 长度相同的字符串比大小，就是纯粹的数值比大小，不用考虑位数问题。这一点非常关键—— 如果长度不同，「位数多的更大」和「字典序更大」就不一定一致了。
2. 它回答的正是题目要问的问题。题目要总长度最大，而在「a 在前」和「b 在前」之间二选一时， 局部最优就是选拼接串更大的那种排法。当这个「两两比较」规则被 sort 全局应用之后，得到的整体拼接串就是最大的。
3. 它满足严格弱序：当 a+b == b+a 时（比如 a=b，或者 {"12","1212"} 这种）， cmp 两边都返回 false，视为「等价」。所以它可以安全地交给 sort。

3
13 312 343

34331213

4
7 13 4 246

7424613

样例 1：343 > 312 > 13（两两拼接比较后），拼成 34331213。
样例 2：顺序是 7、4、246、13 → 拼成 7424613。

完整代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string s[25];

// ★ 核心比较规则：如果 a 接在 b 前面比 b 接在 a 前面更大，a 就排在前面
bool cmp(const string &a, const string &b){
    return a + b > b + a;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> s[i];

    sort(s, s + n, cmp);

    for(int i = 0; i < n; i++) cout << s[i];
    cout << endl;
    return 0;
}

读入直接读成 string，不做任何转换——因为最后要的就是拼接出来的字符串， 中间用不用 int 根本没意义，而且 int 也存不下 10 位数拼起来的结果。

易错点

• 用 int / long long 去拼：20 个数各 10 位，拼起来最多 200 位， 什么整数类型都存不下，必须用 string。
• cmp 写成 a > b（字典序降序）：样例能过，隐藏数据必挂，见上面的反例。
• cmp 写成 a + b >= b + a：多了个等号，破坏严格弱序，属于未定义行为， 可能崩也可能排错。必须用严格的 >。
• cmp 里反复做字符串拼接在数据量大时会有开销，但本题 n ≤ 20，完全无所谓。
• 输出是一个整数（没有空格、没有换行分组），别在中间加空格——加了就变成另一个东西了。

题意：n 个候选人，每人有一个票数，票数可能非常大（最多 100 位）。 输出票数最多的那个人的号数（第几行输入的），再输出他的票数。保证没有并列。

思路：大数比大小，两步走

实现上用「打擂台」比排序更简单，毕竟 n 只有 20：

1. 读第一个候选人，把他当擂主（记住他的字符串和号数）。
2. 后面每个人来挑战：先比长度，长度相同再比字典序，赢了就换擂主。
3. 最后输出擂主的号数和票数。

5
98765
12365
87954
1022356
985678

4
1022356

5 个票数里，1022356 是唯一一个 7 位数，其他都是 5 位或 6 位数，所以位数最多的一定最大 → 第 4 个人当选。这题样例本身就体现了「先比长度」的重要性：985678（6 位）比 98765（5 位）大， 但比 1022356（7 位）小。

完整代码

#include <iostream>
#include <string>
using namespace std;

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

    string best = "";       // 目前票数最多的那个数
    int bestId = 0;         // 它的号数

    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;

        bool better = false;
        if(bestId == 0){
            better = true;                                  // 第一个候选人，直接当擂主
        }else if(s.size() != best.size()){
            better = (s.size() > best.size());              // ① 位数多的数一定更大
        }else{
            better = (s > best);                            // ② 位数相同，用字典序比
        }

        if(better){
            best = s;
            bestId = i;
        }
    }

    cout << bestId << endl;
    cout << best << endl;
    return 0;
}

易错点

• 用 long long 读票数：100 位数字直接溢出，读进来就是垃圾值。必须用 string。
• 只按字典序比、忘了先比长度："9" 会被判为大于 "10"，答案就错了。
• 把号数搞成 0-based：输出要求的是「第一个候选人到第 n 个候选人」，第一行是 1 不是 0。
• 并列怎么办：题面保证不存在票数相同的候选人，所以不用处理。 如果真遇到，用严格大于（better 只在严格更大时为 true）就会保留靠前的那位。

题意：一条桥最多容纳两节车厢，转 180 度就能交换相邻两节车厢。 要用这个操作把车厢按编号从小到大排好，问最少要转多少次。

思路：把「旋转」翻译成「相邻交换」

题目绕了一大圈，本质就是一句：你有一个操作，可以交换数组里相邻的两个元素，问最少几次能让数组升序。

而「最少次数」这个问题的答案非常干净：

所以这题的代码骨架就是「冒泡排序 + 一个计数器」。N ≤ 1000 时 O(N²) 是 10⁶ 次操作，轻松通过。

4
4 3 2 1

6

4 3 2 1 的逆序对：(4,3)(4,2)(4,1)(3,2)(3,1)(2,1)，共 6 对 → 需要 6 次旋转。也可以手数：第一轮 3 次交换、第二轮 2 次、第三轮 1 次，3+2+1 = 6。

完整代码（冒泡，最简单）

#include <iostream>
#include <algorithm>
using namespace std;

int a[1005];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];   // cin 自动跳过换行，分行输入也不怕

    int cnt = 0;
    // 冒泡排序：每一轮把当前最大的车厢「冒」到最右边
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - 1 - i; j++){
            if(a[j] > a[j+1]){          // 相邻两节逆序，必须旋转一次
                swap(a[j], a[j+1]);
                cnt++;                  // 每交换一次记一步
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

进阶版：归并排序数逆序对（O(N log N)）

如果 N 变成 10⁵，冒泡的 O(N²) 就超时了。这时用归并排序，在合并两段的时候顺手把逆序对统计出来：

#include <cstdio>
#include <iostream>
using namespace std;

int a[1005], tmp[1005];
long long cnt = 0;          // 逆序对个数

// 归并排序：顺便统计跨越左右两半的逆序对
void mergeSort(int l, int r){
    if(l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]){
            tmp[k++] = a[i++];
        }else{
            tmp[k++] = a[j++];
            cnt += (mid - i + 1);   // 左半段剩下的 i..mid 全都比 a[j] 大
        }
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r)   tmp[k++] = a[j++];
    for(int t = l; t <= r; t++) a[t] = tmp[t];
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    mergeSort(0, n - 1);
    cout << cnt << endl;
    return 0;
}

易错点

• 用 getline 读数据：题面明说数据可能分行，分行读会把一行当成一整份，直接错。 用 cin >> 或 scanf 逐个读数字最稳。
• 把 1005 写成 1000：N 最大 1000，数组至少要 a[1001]，开 a[1005] 更保险。
• 以为要「排序后输出」：题目只要输出次数，不要输出排好序的车厢序列。
• 内层循环边界写成 j < n - 1 而不是 j < n - 1 - i： 多跑一些不影响正确性（只是慢一点），但内层访问到 a[n] 就越界了，必须带 - i。
• 以为「最少」是随便走走看运气：这题答案是确定的（逆序对数），不需要搜索。