ZeroJudge 解題筆記：k865. 7.幼稚園 (Kindergarten)

作者：王一哲
日期：2025年5月12日



ZeroJudge 題目連結：k865. 7.幼稚園 (Kindergarten)

解題想法

我是用兩層的 for 迴圈，先讀取第 i 個人的身高 h，裡面再用兩個 for 迴圈，分別向左、向右找較高的人，取向左、向右交換次數較少者。這樣的寫法效率不夠高，Python 過不了，C++ 可以通過測試。

Python 程式碼

速度太慢，只能通過 40% 的測資，需要再找到更有效率的寫法。

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    hs = list(map(int, input().split()))  # 身高
    ans = 0  # 交換次數
    for i, h in enumerate(hs):  # 讀取第 i 個人的身高 h
        toleft = 0  # 向左找較高的人數
        for j in range(i-1, -1, -1):
            if hs[j] > h: toleft += 1
        toright = 0  # 向右找較高的人數
        for j in range(i+1, n):
            if hs[j] > h: toright += 1
        if toleft <= toright: ans += toleft  # 取向左、向右交換次數較少者
        else: ans += toright
    print(ans)

C++ 程式碼

使用時間約為 39 ms，記憶體約為 116 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n;  // n 個人
    while(scanf("%d", &n) != EOF) {
        int hs[n];  // 身高
        for(int i=0; i<n; i++) scanf("%d", &hs[i]);
        int ans = 0;  // 交換次數
        for(int i=0; i<n; i++) {  // 讀取第 i 個人的身高 h
            int toleft = 0, toright = 0;
            for(int j=i-1; j>=0; j--) {  // 向左找較高的人數
                if (hs[j] > hs[i]) toleft++;
            }
            for(int j=i+1; j<n; j++) {  // 向右找較高的人數
                if (hs[j] > hs[i]) toright++;
            }
            if (toleft <= toright) ans += toleft;  // 取向左、向右交換次數較少者
            else ans += toright;
        }
        printf("%d\n", ans);
    }
    return 0;
}