d045 - 11222 - Only I did it!
題目描述
題目描述了三個朋友各自解了一些題目，要求找出哪位朋友解的題目數量最多，且這些題目是其他兩位朋友都未曾解過的。如果有多位朋友解的題目數量相同，則按照編號順序輸出。
解題思路
解題思路是分別統計每位朋友獨自解出的題目數量。具體步驟如下：
- 讀取三位朋友各自解出的題目，並使用布林陣列
ta,tb,tc記錄每個題目是否被對應的朋友解過。 - 對每位朋友解出的題目進行排序，以便更容易地查找。
- 遍歷每位朋友解出的題目，檢查該題目是否被其他兩位朋友解過。如果沒有，則將該題目計入該朋友的獨自解出的題目數量。
- 找出獨自解出的題目數量最多的朋友，並輸出其編號、數量以及獨自解出的題目列表。如果有多位朋友數量相同，則按照編號順序輸出。
複雜度分析
- 時間複雜度: O(N * M + M log M)，其中 N 是每位朋友解出的題目數量，M 是題目範圍 (10000)。排序佔據 O(M log M)，遍歷和查找佔據 O(N * M)。
- 空間複雜度: O(M)，主要用於儲存布林陣列
ta,tb,tc。
程式碼
#include <bits/stdc++.h>
using namespace std;
int t,a[1005],b[1005],c[1005],na,nb,nc;
bool ta[10005],tb[10005],tc[10005];
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> t;
for(int ca=1;ca<=t;++ca){
memset(ta,0,sizeof(ta));
memset(tb,0,sizeof(tb));
memset(tc,0,sizeof(tc));
cin >> na;
int sa=0,sb=0,sc=0,ma=0;
for(int i=0;i<na;++i){
cin >> a[i];
ta[a[i]]=1;
}
cin >> nb;
for(int i=0;i<nb;++i){
cin >> b[i];
tb[b[i]]=1;
}
cin >> nc;
for(int i=0;i<nc;++i){
cin >> c[i];
tc[c[i]]=1;
}
sort(a,a+na);
sort(b,b+nb);
sort(c,c+nc);
for(int i=0;i<na;++i){
if(!tb[a[i]]&&!tc[a[i]])++sa;
}
for(int i=0;i<nb;++i){
if(!ta[b[i]]&&!tc[b[i]])++sb;
}
for(int i=0;i<nc;++i){
if(!ta[c[i]]&&!tb[c[i]])++sc;
}
ma=max(sa,max(sb,sc));
cout << "Case #" << ca << ":\n";
if(ma==sa){
cout << "1 " << ma;
for(int i=0;i<na;++i){
if(!tb[a[i]]&&!tc[a[i]])cout << " " << a[i];
}
cout << "\n";
}
if(ma==sb){
cout << "2 " << ma;
for(int i=0;i<nb;++i){
if(!ta[b[i]]&&!tc[b[i]])cout << " " << b[i];
}
cout << "\n";
}
if(ma==sc){
cout << "3 " << ma;
for(int i=0;i<nc;++i){
if(!ta[c[i]]&&!tb[c[i]])cout << " " << c[i];
}
cout << "\n";
}
}
}