题解：P13133 [GCJ 2018 Qualification] Trouble Sort

chinazhanghaoxun · 2025-08-04 20:55:53 · 题解

P13133 Trouble Sort - Solution

Problem Statement

给定一个整数序列 V，现在对 V 中的每一组 V_i 和 V_{i+2} 进行排序操作，其中 i\in [1,n-2]。

问按照这个方式排序出来的序列是否有序，如果无序，求出第一个错误的下标 i。

Analysis

不难发现，这样的排序方法其实就是分别将奇数下标的元素排序，偶数下标的元素排序，我们只需要判断是否会产生冲突就可以了。

Approach

读入时直接分别加入到 odd 和 even 两个数组，分别排序，然后再合并到同一个数组中。要考虑 N 的奇偶性，注意细节。然后判断这是否是一个顺序正确的序列即可。

Code

#include<bits/stdc++.h>
using namespace std;
int n,t;
int main(){
    cin>>t;
    for(int cs=1;cs<=t;cs++){
        vector<int> a,b; 
        cin>>n;
        a.push_back(-1); //用于占位 
        b.push_back(-1);
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            if(i%2) a.push_back(x); //奇数下标给 a 
            else b.push_back(x); //偶数下标给 b 
        }
        sort(a.begin(),a.end()); //分别排序 
        sort(b.begin(),b.end());
        vector<int> c;
        for(int i=1;i<=n/2;i++){ //合并操作 
            c.push_back(a[i]);
            c.push_back(b[i]);
        }
        if(n%2) c.push_back(a[n/2+1]); //剩下一个手动加入 

        printf("Case #%d: ",cs);
        bool fl=0;
        for(int i=0;i<c.size()-1;i++){
            if(c[i]>c[i+1]){ //发现错误 
                cout<<i<<endl;
                fl=1;
                break;
            }
        }
        if(!fl)
            puts("OK");
    }
    return 0;
}