题解：P13257 [GCJ 2014 #2] Up and Down

_DATA_X_ · 2025-09-10 16:30:20 · 题解

P13257 题解：

主要思路：

循环处理每次输入的 n 个数，每次处理找这组数中的最小值，将这个最小值放在离它最近的边界处，然后这个数就已经处理好了，将其从数组中删除，同时用一个变量累加每次将最小值放在离它最近的边界的最小交换次数，最后输出这个变量即可。

代码实现：

• 定义一个变量 ans 存储最终结果。
• 进入内部循环，每次循环找现存的数中的最小值，存储它的位置，然后让 ans 加上把最小值放在离最小值最近的边界的交换次数，即 ans+=min(id-1,i-id); 将当前的最小值删除。
• 输出 ans 即为最终结果。

AC Code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=1e3+7;
int t,n,a[N];
int32_t main(){
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    cin>>t;
    for(int res=1;res<=t;res++){
        cin>>n;
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int ans=0;//存最终结果
        for(int i=n;i>=1;i--){
            int mi=INT_MAX,id;
            for(int j=1;j<=i;j++){
                if(a[j]<mi){
                    mi=a[j];
                    id=j;//取最小值的下标
                }
            }
            ans+=min(id-1,i-id);//加上交换次数
            for(int j=id+1;j<=i;j++){
                a[j-1]=a[j];
            }//将当前最小值删除
        }
        cout<<"Case #"<<res<<": "<<ans;//输出答案
        if(res!=t) cout<<endl; 
    }
    return 0;//完结撒花！！！
}

感谢阅读。

最后，留个赞再走吧。