UVa 10057

題目

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

給一個長度為 $n$ 的序列，求序列的 最小中位數、中位數個數、所有符合中位數的正整數

想法

1. 最小中位數
   序列經過排序後最中間的值就是答案

   當序列長度是偶數時，中間兩個數字間的最小值就是答案

2. 中位數個數
   如果序列長度是偶數，並且中間兩個元素 $a, b$ 是不同的，因為 $a, b$ 都可以是中位數，所以序列中 $a, b$ 的數量總和就是答案

   如果沒有不同的兩個元素或是序列長度是奇數，那麼只需要找 $a$ 的數量總和即可

3. 所有符合中位數的正整數(不重複)
   如果序列長度是奇數，因為只有最中間的值可以是中位數，所以答案必定是 $1$

   在偶數的狀況下，我們只需要計算中間兩個元素之間包含自己本身總共有多少元素即可

Code

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, B, C, Min, Max, arr[1000010];
int main(){
	while(cin>>n){
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		sort(arr, arr+n);
		
		// 先找到最小/最大中位數，順便求出第三個答案
		if(n%2 == 0){
			Min = arr[n/2-1];
			Max = arr[n/2];
			C = Max - Min + 1;
		}
		else{
			Min = arr[n/2];
			Max = arr[n/2];
			C = 1;
		}
		
		// 中間有不同的兩個元素
		// 計算個數可以直接用二分搜找到數量，也可以用暴力找
		if(n%2 == 0 && arr[n/2-1] != arr[n/2])
			B = upper_bound(arr, arr+n, Min) - lower_bound(arr, arr+n, Min) + upper_bound(arr, arr+n, Max) - lower_bound(arr, arr+n, Max);
		else
			B = upper_bound(arr, arr+n, Min) - lower_bound(arr, arr+n, Min);
		cout<<Min<<" "<<B<<" "<<C<<"\n";
	}

	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

每筆測資排序時間複雜度為 $O(nlogn)$

每筆測資找到 $A$ 以及 $C$ 的時間複雜度都是 $O(1)$

每筆測資找到 $B$ 的時間複雜度最差為 $O(4logn)$

每筆測資總時間複雜度約為 $O(n + 5logn)$