题目链接

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代码

CPP

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

题解：P13133 [GCJ 2018 Qualification] Trouble Sort

文章操作

题目链接

Solution

题意分析

解法

AC代码

相关推荐

评论

题解：P13133 [GCJ 2018 Qualification] Trouble Sort