競程作業，2017 交大年度賽 Problem F：FOJ-210
這題我一直理解錯誤，結果卡很久
重新看題目之後才發現其實蠻簡單的
他是說這個國會裡面可能會存在一個小圈圈
這個小圈圈裡面的每一個人，都對圈外的每一個人有控制權
（我一直以為圈內的人也要能互相控制之類的 QQ
然後找到最小的圈圈就好了
所以就先找出當時最有 Power 的人（對最多人有控制權的人
然後剩下他沒辦法控制的人，就一定要跟他一組
然後開始找這些人裡面最有 Power 的人做一樣的事
然後一直重複作就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n, tmp, ans=0, ttmp=0;
cin>>n;
bool fl[204];
for(int i=1; i<=203; i++){
fl[i] = 0;
}
for(int i=0; i<n; i++){
cin>>tmp;
fl[tmp] = 1;
}
for(int i=2; i<=203; i++){
if(fl[i]){
ttmp++;
}
else{
ans+=(ttmp+1)/2;
ttmp=0;
}
}
cout<<ans<<"\n";
}
}
|