###### tags: `F408` `C`
# F408. 迷你蘋果鎮
## 題目描述
### 內容
迷你蘋果鎮住著許多黑人與白人家庭。在一次白人警察的過度執法導致一名黑人嫌犯死亡後，引起了大規模的暴力抗議行動。

在抗議行動平息之後，為了避免白人家庭與黑人家庭之間發生衝突，鎮長要求警察局在每個白人家庭與黑人家庭之間設置巡邏哨。警察局已經從戶政單位取得了所有住戶的地址及膚色，以便計算巡邏哨的數量及預估所需經費。

一般街道門牌編號會依大小順序排列，方便人們找地址，但是戶政機關的資料卻可能是按姓名、身分證號碼、生日或其他屬性來排序的。現在，給你某條街道單側所有住戶的門牌號碼及膚色，要麻煩你幫忙整理一下並計算這條街道該側需要設置幾個巡邏哨。
### 輸入說明
輸入只有兩行，第一行含有一個整數 n (1 ≤ n ≤ 1000)，代表這條街道該側有幾個住戶。
第二行則有 n 個以空白隔開的整數 fi (-46000 ≤ fi ≤ 46000，1 ≤ i ≤ n)，
負數代表白人家庭，正數代表黑人家庭，絕對值則是他們的門牌號碼。
### 輸出說明
請輸出一個整數，代表需要設置幾個巡邏哨。
### 評分說明
無
### 範例
測資 1：

3
1 3 -5
輸出 1：

1
測資 2：

4
-9 -5 -1 3
輸出 2：

2
***
## 題目思索
從題目敘述中可將它們設為住戶個數n、巡邏哨個數sum，再指定數據陣列h[n]，數據的絕對值abs(h[])則為門牌號碼。

int n, sum = 0;
scanf("%d", &n);
int h[n];
for(int i = 0; i < n; i++)
    scanf("%d", &h[i]);

先將它們依照abs(h)由小到大排列好。

for(int i = 0; i < n - 1; i++)         //加減交換法
    for(int j = 0; j < n - i - 1; j++)
        if(abs(h[j]) > abs(h[j + 1])){
            h[j] = h[j] + h[j + 1];
            h[j + 1]= h[j] - h[j + 1];
            h[j] = h[j] - h[j + 1];
        }

整理後從起始點 h[0] 到 h[n - 1] 中，判斷此住戶與下一個住戶是否有相異的正負號。

for(int i = 0; i < n - 1; i++){
    if(h[i] > 0 && h[i + 1] < 0)         //若此為正，下一戶為負
        sum++;
    else if(h[i] < 0 && h[i + 1] > 0)    //若此為負，下一戶為正
        sum++;
}

最後再輸出sum即可。
***
### 初稿程式碼

#include <stdio.h>
#include <string.h>
int main(){
    int n, sum = 0;
    scanf("%d", &n);
    int h[n];
    for(int i = 0; i < n; i++)
    scanf("%d", &h[i]);

    for(int i = 0; i < n - 1; i++)
        for(int j = 0; j < n - i - 1; j++)
            if(abs(h[j]) > abs(h[j + 1])){
                h[j] = h[j] + h[j + 1];
                h[j + 1]= h[j] - h[j + 1];
                h[j] = h[j] - h[j + 1];
            }

    for(int i = 0; i < n - 1; i++){
        if(h[i] > 0 && h[i + 1] < 0)
            sum++;
        else if(h[i] < 0 && h[i + 1] > 0)
            sum++;
    }
    printf("%d", sum);
    return 0;
}

### 測試結果

***
## 成果
### 程式碼

#include <stdio.h>
#include <string.h>
int main(){
    int n, sum = 0;
    scanf("%d", &n);
    int h[n];
    for(int i = 0; i < n; i++)
    scanf("%d", &h[i]);
    for(int i = 0; i < n - 1; i++)
        for(int j = 0; j < n - i - 1; j++)
            if(abs(h[j]) > abs(h[j + 1])){
                h[j] = h[j] + h[j + 1];
                h[j + 1]= h[j] - h[j + 1];
                h[j] = h[j] - h[j + 1];
            }
    for(int i = 0; i < n - 1; i++){
        if(h[i] > 0 && h[i + 1] < 0)
            sum++;
        else if(h[i] < 0 && h[i + 1] > 0)
            sum++;
    }
    printf("%d", sum);
    return 0;
}

### 解題
***
## 反思
這次思路比較單純，測資限制裡也沒有溢位的問題，所以解題的時間相對減少，但為了保險起見，還是需要透過較龐大的測資測試過，方可確認程式執行無誤。
### 心智圖

***
## 題目來源
[f408. 迷你蘋菓鎮(from Zero Judge)](https://zerojudge.tw/ShowProblem?problemid=f408)

2023-11-13 編寫此文
2023-11-19 調整結構
2023-12-10 文法勘誤