e796 - p3. 站牌廣告
題目描述
題目要求計算公車路線上每個站牌的人流量，並找出人流量最少和最多的站牌編號。輸入包含站牌總數 B 和乘客數量 P。接下來 P 行，每行包含兩個數字 X 和 Y，表示一位乘客的上車站牌和下車站牌。
解題思路
本題的核心思路是使用一個陣列 a 來記錄每個站牌的人流量。遍歷所有乘客的上下車資訊，對於每位乘客，將其上車站牌和下車站牌之間（包含上下車站牌）的所有站牌的人流量加 1。然後，遍歷 a 陣列，找出人流量的最小值和最大值，並記錄對應的站牌編號。最後，輸出人流量最少的站牌編號和人流量最多的站牌編號。如果有多個站牌具有相同的人流量，則輸出編號最小的（最少人流）和最大的（最多人流）。
複雜度分析
- 時間複雜度: O(B * P + B) 其中 B 是站牌數量，P 是乘客數量。遍歷乘客資訊需要 O(B * P) 的時間，遍歷站牌陣列找出最大最小值需要 O(B) 的時間。
- 空間複雜度: O(B) 需要一個大小為 B+1 的陣列
a來儲存每個站牌的人流量。
程式碼
#include <stdio.h>
int main(){
int b,p,x,y;
scanf("%d%d",&b,&p);
int a[b+1],max=0,min=1000;
for(int i=0;i<=b;i++)
a[i]=0;
while(p--){
scanf("%d%d",&x,&y);
if(y<x){
x^=y;
y^=x;
x^=y;
}
for(int i=x;i<=y;i++)
a[i]++;
}
for(int i=1;i<=b;i++){
if(a[i]>max)
max=a[i];
if(a[i]<min)
min=a[i];
}
for(int i=1;i<=b;i++){
if(a[i]==min){
printf("%d ",i);
break;
}
}
for(int i=b;i>=0;i--){
if(a[i]==max){
printf("%d",i);
break;
}
}
}