ZeroJudge 解題筆記：f408. 迷你蘋菓鎮

作者：王一哲
日期：2025年10月9日


ZeroJudge 題目連結：f408. 迷你蘋菓鎮

解題想法

將所有的門牌依照絕對值排序，再依序掃過每一個門牌，如果跟相鄰的門牌相乘小於 0 則答案加 1。

Python 程式碼

使用時間約為 19 ms，記憶體約為 3.4 MB，通過測試。

n = int(input())
arr = list(map(int, input().split()))
arr.sort(key = lambda x : abs(x))
cnt = 0
for i in range(1, n):
    if arr[i-1] * arr[i] < 0:
        cnt += 1
print(cnt)

C++ 程式碼

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

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    int arr[n];
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    sort(arr, arr+n, [] (int a, int b) {
        return abs(a) < abs(b); } );
    int cnt = 0;
    for(int i=1; i<n; i++) {
        if (arr[i-1] * arr[i] < 0) cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> arr (n);
    for(int i=0; i<n; i++) cin >> arr[i];
    sort(arr.begin(), arr.end(), [] (int a, int b) {
        return abs(a) < abs(b); } );
    int cnt = 0;
    for(int i=1; i<n; i++) {
        if (arr[i-1] * arr[i] < 0) cnt++;
    }
    cout << cnt << "\n";
    return 0;
}