f408 - 迷你蘋菓鎮

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一條街道上黑人家庭和白人家庭之間需要設置的巡邏哨數量。街道上的住戶資訊以門牌號碼和膚色表示，其中負數代表白人家庭，正數代表黑人家庭，絕對值代表門牌號碼。

解題思路

解題思路是先將住戶按照門牌號碼的絕對值排序。然後，遍歷排序後的住戶列表，如果相鄰兩個住戶的膚色不同（一個是黑人家庭，另一個是白人家庭），則需要設置一個巡邏哨。

程式碼首先讀取住戶數量 n，然後讀取每個住戶的膚色資訊 a[i]。接著，使用 sort 函數按照門牌號碼的絕對值對住戶列表進行排序。最後，遍歷排序後的住戶列表，如果相鄰兩個住戶的膚色不同，則將巡邏哨數量 ans 加一。

複雜度分析

• 時間複雜度: O(n log n)
• 空間複雜度: O(n)

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int a[1005],ans;
bool cmp(int x,int y){
	if(abs(x)>abs(y))return 1;
	return 0;
}
int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;++i)
		cin >> a[i];
	sort(a,a+n,cmp);
	for(int i=0;i<n;++i)
		if(i&&a[i]*a[i-1]<0)
			++ans;
	cout << ans;
}