UVa11875 - Brick Game (水題)

題目大意

孟加拉國對於 Brick Game 非常熱衷,最近出現了電競的賽事,隊伍的隊員數量必定是奇數,且透過年齡進行排序,可能會給遞增或遞減。需要一個隊長且隊長年齡必須是隊伍的中間值,否則會出現代溝,請輸出隊長的最適合年齡。

P.S. 隊友年齡都是獨一無二,不會有另外一個隊友與其他隊友年齡相同。

分析

水到不行www,前題是你英文夠好的話…。我就理解錯了方向,還我寫了一個錯誤的版本

由於題目的隊員數量必定是奇數因此不需要擔心偶數 / 2 的問題,再加上年齡一定是遞增或是遞減,在奇數情況時連排序都不需要www。

偶數的情況 - 題目沒有用到

偶數比較麻煩,假如 1,2,3,4 我們要找出隊長就有可能是 2,3,但因為題目是奇數所以就不用擔心了XD。

假如隊長改成偶數且年齡必須是等於或等於 + 1 的年齡這時候排序就會很重要,不然直接輸入至陣列時就會因為沒有排序,如果同筆測試資料只是順序遞增與遞減時輸出答案就會不一至。

舉例: 1,2,3,4 and 4,3,2,1 如果隊員是偶數時則選中位數 + 1 的隊友

同樣放在題目的這份程式碼,公式是 \(n/2+1\),那在這兩種順序就會輸出 2 或者 3,答案不一致。

錯誤方向

擷取題目的關鍵字,這是誤導我的方向

Hence they select the captain of a team in such a way so that the number of player in the team who are younger than that captain is equal to the number of players who are older than that captain

因此選擇一個隊長的方法是選擇一位隊員且此隊員年齡會是隊伍的中間值
P.S. 中間值 = 中位數。

我把它理解成了平均值…,於是我就用了加權平均數去計算,再找出最靠近加權平均數的年齡,後來才發現她要的是中位數..。

觀念重點

  • 先將隊員年齡放入陣列中(index 0),在 \(n/2\) 即可。

參考來源

  • 齊笎詳解

心得

這題不難拉,只需要解決英文問題就好了,最近都在訓練數學題目順便增強英文閱讀能力,最近覺得英文閱讀能力有變好,算是一大感動嘛XD

可是我已經連續兩題英文閱讀方向錯了…,可以給我翻譯蒟蒻嘛。

題目程式碼

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
#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 15
#define oo 1e9
using namespace std;
int num[MAXN] ;
int t , n ;
int kase ;

int compute(){
for(int i = 0 ; i < n ; i++){
cin >> num[i] ;
}
//sort(num,num+n);

return num[n/2] ;
}


int32_t main()
{
#ifdef LOCAL
freopen("in1.txt" , "r" , stdin );
freopen("out.txt" , "w" , stdout);
#endif // LOCAL

cin >> t ;
while(t--){
cin >> n ;
cout << "Case " << ++kase << ": " << compute() << '\n' ;
}

return 0;
}
  • 版權聲明: 本部落格所有文章除有特別聲明外,均採用 Apache License 2.0 許可協議。轉載請註明出處!
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV: