Koios1143的筆記

Zerojudge c296

發表於 更新於 分類於 ，

Zerojudge c296

題敘

https://zerojudge.tw/ShowProblem?problemid=c296
有 $N$ 個人圍成一圈，編號 $1$ ~ $N$，從編號 $1$ 開始每 $m$ 回合後從開頭數過來第 $m$ 個人會被淘汰，下一回合從被淘汰的下一個人開始
問經過 $k$ 回合後最後被淘汰的下一個人標號為多少

想法

暴力(45%)

一開始最好想到的就是跟著模擬一遍，大概會是長這樣子
利用編號必定會是遞增的特性，搭配sort可以使每次只需花費 $O(nlogn)$ 的時間

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,m,k;
vector<pii> v;
int main(){
	IOS
	cin>>n>>m>>k;
	for(int i=1 ; i<=n ; i++) v.emplace_back(i,i);
	int last=0;
	while(k--){
		last=(last+m-1)%n;
		n--;
		v[last].first=INT_MAX;
		sort(v.begin(),v.end());
	}
	cout<<v[(last)%n].second<<"\n";
	return 0;
}

觀察規律

觀察原序號與新序號的關係(假設都從0開始)
例如: 當現在 $n=5, m=2, k=4$

  • 第一輪
    $1$ 號被淘汰
上一輪編號 0 1 2 3 4
新編號 3 - 0 1 2
  • 第二輪
    $2$ 號被淘汰(上一輪編號)
上一輪編號 3 - 0 1 2
新編號 1 - 2 - 0
  • 第三輪
    $0$ 號被淘汰(上一輪編號)
上一輪編號 1 - 2 - 0
新編號 - - 0 - 1
  • 第四輪
    $1$ 號被淘汰(上一輪編號)
上一輪編號 - - 0 - 1
新編號 - - 0 - -

觀察編號之間的關係，可以發現到因為循環的關係，舊編號 = (新編號+m)%舊人數
因此，只要解決第 $k$ 輪的問題，第 $k-1$ 輪的答案也就出來了，再來遞迴求解即可

Code

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
//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,m,k;
int solve(int people, int last){
	if(last==1){
		int res=m%people;
		return res;
	}
	if(last==n){
		int res=(solve(people-1, last-1)+m+1)%people;
		return res;
	}
	else{
		int res=(solve(people-1, last-1)+m)%people;
		return res;
	}
}
int main(){
	IOS
	cin>>n>>m>>k;
	cout<<solve(n,k)+1<<"\n";
	return 0;
}

複雜度

遞迴總共有 $k$ 層，每層的時間複雜度為 $O(1)$
總時間複雜度為 $O(k)$