e546 - 12650 - Dangerous Dive
題目描述
題目要求找出在潛水任務中犧牲的志願者ID。給定前往任務的志願者總數 N 和返回的志願者數量 R，以及返回志願者的ID列表，需要輸出未返回的志願者ID，並按升序排列。如果所有志願者都返回，則輸出 "*”。
解題思路
這題的核心是找出兩個集合的差集。第一個集合是所有志願者的ID（從1到N），第二個集合是返回的志願者的ID。通過遍歷返回的志願者ID，將其標記為已返回，然後遍歷所有志願者ID，輸出未被標記為已返回的ID。如果所有志願者都返回，則直接輸出 "*”。
複雜度分析
- 時間複雜度: O(N + R)
- 空間複雜度: O(N)
程式碼
#include <stdio.h>
int main(){
int a,b;
while(scanf("%d%d",&a,&b)>0){
if(a==b){
printf("*\n");
while(a--)
scanf("%d",&b);
}
else{
int c[a+1]={0},n;
while(b--){
scanf("%d",&n);
c[n]=1;
}
for(int i=1;i<=a;i++){
if(c[i]==0)
printf("%d ",i);
}
printf("\n");
}
}
}