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

Dustlpes_CZY · 2025-12-11 22:24:18 · 题解

题目大意

给你 T 组数据，每组数据由长度 N 和长度为 N 且由互不相同的整数构成的序列 A = [A_1,A_2,...,A_N] ，通过若干次 swap 使得序列变成先升后降的序列，求最小交换次数。

思路

刚开始看到黄题以为需要找到关键字 m 来解决这道题，可不然。 我们可以从先升后降这一点出发，如果 a_i 是最小的数，但 a_i 处于 a_2 到 a_{n-1} 中时，我们就要让它远离中心位置 a_m (大数)，从而开始交换！

以样例 A=[1,8,10,3,7] 为例：

• 最小值 = A_1 = 1，此时已经处于序列的头，交换次数为 0 。
• 最小值 = A_4 = 3，此时处于 a_2 到 a_{n-1} 中，则我们要让它交换到 A_1 or A_n ，此时到 A_n 比到 A_1 移动距离短，所以交换到 A_n 交换次数为 1 。
• 最小值 = A_4 = 7，满足“先升后降”条件，交换次数为 0，此时序列 A 为 [1,8,10,7,3] 满足“先升后降”所以之后交换次数全为 0，答案为 1，正确。

理论存在，实践开始！

AC CODE

(相必诸位最想看这个吧，我也是)

#include <bits/stdc++.h>
#include <algorithm>
#define LL long long
#define the return 
#define in(x) LL x; cin>>x;
#define lop(x,a,b,c) for(LL x=a; b-x+c; x+=c)
using namespace std;
const LL N=1919810;
LL ans,a[N];
void solve(LL ansi){ ans=0;
    in(n);
    lop(i,1,n,1) cin>>a[i];
    while(n){ 
        LL mi=1234567891,mini=114514; 
        //温知识: 1234567891 是质数
        lop(i,1,n,1) if(a[i] < mi){
            mi=a[i]; mini=i;//找出最小值并记录
        }
        ans+=min(mini-1,n-mini);//两边取最近
        // mini-1 是1--mini移动距离,n-mini 是到 n 的距离
        lop(j,mini,n-1,1) swap(a[j],a[j+1]);//swap
        n--;//删除 mini ,mini 已经用不到了
    }
    printf("Case #%lld: %lld\n",ansi,ans); 
    the ;
}
int main(void){ cin.tie(0)->sync_with_stdio(0);//美妙的 ios
    in(k); 
    lop(i,1,k,1) solve(i);
    the 0;
}

写在最后： 这是本人的第一篇题解！！！赏个赞再走吧！ （管理员大大辛苦了！）