Koios1143的筆記

Kattis - Conformity

發表於 分類於

Kattis - Conformity (UVa 11286)

題目

https://open.kattis.com/problems/conformity

http://domen111.github.io/UVa-Easy-Viewer/?11286

在一間大學當中有 $n$ 個學生，每個學生都可以選擇 5 種課程，並且課程以介於 $100$ ~ $499$ 之間的數字表示

每個學生選擇的課程會形成一個課程組合

現在學校想要統計每種課程組合有多少學生選擇，並且表揚那些選擇最受歡迎課程組合的學生

輸出總共要表揚多少學生

$1 \leq n \leq 10000$

想法

首先我們要先界定一下相同的課程組合，只要選擇的課程內容相同就是同一個課程組合

但是選擇的先後順序不同會讓我們很困擾，所以首先將所有學生選擇的課程按照其編號由小到大排序好

接下來，對我們來說全部學生的課程組合就是一群無序的資料了，針對這群無序的資料可以觀察排序後有沒有甚麼好的性質可以使用

我們會發現到，當我們將這群資料由小到大排序後，相同的課程組合會被放在一起

那麼我們只需要去統計這幾群相同的序列(相同的課程組合)總共有多少組，然後記錄下最多組的人數總和即可

那麼，要怎麼排序這群無序的資料呢?

一種方法是很直觀的依序依照每個元素的大小來排序，自訂一個 compare function

另一種想法是這樣的，首先觀察到每個學生只能選擇 $5$ 種課程，並且課程編號都是 $3$ 位數

那麼，將這些數字組合起來會是一個 $15$ 位數的數字，範圍在 long long 內

這樣就可以將這一群資料變成一個序列了!

詳細來說，我們的步驟是這樣

  1. 輸入
  2. 將每一位學生選擇的課程由小到大排序
  3. 將每個學生的課程組合組成一個 $15$ 位數的數字
  4. 將課程組合由小到大排序
  5. 從第 $1$ 個課程組合開始遍歷
    • 如果課程組合 $i$ 和課程組合 $i-1$ 相同
      將計數器 $+1$
    • 如果課程組合 $i$ 和課程組合 $i-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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, arr[10000][5];
long long num[10000];
int main(){
	cin>>n;
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<5 ; j++){
			cin>>arr[i][j];
		}
		// 先將每個學生的課程排序
		sort(arr[i], arr[i]+5);
		// 再來組合成 15 位數
		for(int j=0 ; j<5 ; j++){
			num[i] *= 100;
			num[i] += arr[i][j];
		}
	}
	// 接著排序所有課程組合
	sort(num, num+n);
	// 先記錄下第一組課程組合
	int Max = 1, ans=1;
	for(int i=1, cnt=1 ; i<n ; i++){
		if(num[i] == num[i-1]) cnt++;
		else{
			if(cnt > Max){
				Max = cnt;
				ans = cnt; // 當前是最新的最大值，答案正是計數器的值
			}
			else if(cnt == Max){
				ans += cnt;
			}
			// 要記錄第 i 個數
			cnt=1;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

複雜度分析

輸入時間複雜度為 $O(n)$

排序所有學生課程的時間複雜度為 $O(5nlog5) \approx O(n)$

所有學生組合成 15 位數的時間複雜度為 $O(5n) \approx O(n)$

排序所有課程組合的時間複雜度為 $O(nlogn)$

遍歷所有課程組合的時間複雜度為 $O(nlogn)$

總時間複雜度為 $O(3n + 2nlogn) \approx O(n + nlogn)$