题解：P13133 [GCJ 2018 Qualification] Trouble Sort

zhanghq2012 · 2025-09-27 22:23:12 · 题解

题目链接

题目传送门

Solution

题意分析

一共有 T 组数据，每组数据给出一个 n，和 n 个数，我们要判断将这 n 个数进行三元组冒泡排序，判断排序后是否有序，如果无序，求出第一个错误的下标 i。

解法

我们分析一下三元组冒泡排序：对于任意 i（1≤i≤n-2），如果 a_i>a_{i+2} 交换 a_i 与 a_{i+2} 的值，那么可以看出 a_i 与 a_{i+2} 一定是同奇或同偶，那么只需将数列中的奇数项和偶数项单独进行排序然后再检查是否有序。

AC代码

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        int n;
        cin>>n;
        vector<int> a,b,c;
        //占位方便后续奇偶判断
        a.push_back(-10);
        b.push_back(-10);
        c.push_back(-10);
        for(int j=1;j<=n;j++){
            int x;
            cin>>x;
            if (j%2==0) {
                b.push_back(x);//b存偶数项
            }
            else {
                c.push_back(x);//c存奇数项
            }
        }
        //排序
        sort(b.begin(),b.end());
        sort(c.begin(),c.end());
        int ans=-1;
        for(int j=1;j<=n/2;j++){
            //合并
            a.push_back(c[j]);
            a.push_back(b[j]);
        }
        if (n%2!=0) a.push_back(c[n/2+1]);
        for (int j=1;j<=n-1;j++) {
            if (a[j]>a[j+1]) {  //排查错误
                ans=j-1;
                break;
            }
        }
        cout<<"Case #"<<i<<": ";
        if(ans!=-1) cout<<ans<<'\n';
        else cout<<"OK\n";
    }
    return 0;
}