e661 - 11875 - Brick Game

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出一個由 N 個成員組成的團隊中，隊長的年齡。團隊成員的年齡以遞增或遞減的順序給定。隊長需要被選出，使得比隊長年輕的成員人數等於比隊長年長的成員人數。

解題思路

由於輸入的年齡序列是嚴格遞增或嚴格遞減的，因此隊長的年齡一定是整個序列的中位數。中位數是將序列排序後位於中間位置的元素。由於序列已經排序（遞增或遞減），可以直接通過索引找到中位數。對於 N 個成員，中位數的索引是 (N - 1) / 2。

複雜度分析

• 時間複雜度: O(N)
• 空間複雜度: O(N)

程式碼

#include <stdio.h>
int main(){
	int t,n;
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		scanf("%d",&n);
		int a[n]={0},m=n;
		while(n--)
			scanf("%d",&a[n]);
		printf("Case %d: %d\n",i,a[m/2]);
	}
}