排序问题总结

P1781 宇宙总统

洛谷题目：比较编号字符串，选出最大者

💡 最终 AC 代码（P1781）

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

struct person{
    int id;
    string num;
};

bool cmp (const person& a,const person& b){
    if(a.num.size()!=b.num.size()){
        return a.num.size()>b.num.size();
    }
    return a.num>b.num;
}

int main(){
    int n;
    cin>>n;
    vector<person> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i].num;
        a[i].id=i+1;
    }
    sort(a.begin(),a.end(),cmp);
    cout<<a[0].id<<endl<<a[0].num;
    return 0;
}

忘记给结构体结尾加分号 };
cin<<a[i].num; 写反了输入输出方向，应该是 cin >>
排序函数传参写成 cmp()，应为 cmp（函数指针）
手动写字符串逐位比较，其实可以直接用 a.num > b.num

利用字符串的默认比较（按字典序 = ASCII）可大幅简化代码；
比较前可以判断字符串长度，避免前导零干扰；
如果涉及更复杂的排序逻辑，建议封装成函数提高可读性；

字符串默认是按字符的 ASCII 值逐位比较的，容易因为前导零或写法不规范出错。

P1908 逆序对（洛谷）

归并排序

排序逆序对

用归并排序统计逆序对，典型分治应用，效率 O(nlogn)

Visit P1908 逆序对（洛谷）

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

static long long t = 0;

void mergeSort(vector<int>& a, vector<int>& b, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(a, b, l, mid);
    mergeSort(a, b, mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) b[k++] = a[i++];
        else {
            b[k++] = a[j++];
            t += (mid - i + 1); // 💡统计逆序对
        }
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= r) b[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = b[p];
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    mergeSort(a, b, 0, n - 1);
    cout << t;
    return 0;
}