題目描述

小涵很喜歡電腦游戲，這些天他正在玩一個(gè)叫做《三國》的游戲。

在游戲中，小涵和計(jì)算機(jī)各執(zhí)一方，組建各自的軍隊(duì)進(jìn)行對(duì)戰(zhàn)。游戲中共有 N 位武將（N為偶數(shù)且不小于 4），任意兩個(gè)武將之間有一個(gè)“默契值”，表示若此兩位武將作為一對(duì)組合作戰(zhàn)時(shí)，該組合的威力有多大。游戲開始前，所有武將都是自由的（稱為自由武將，一旦某個(gè)自由武將被選中作為某方軍隊(duì)的一員，那么他就不再是自由武將了），換句話說，所謂的自由武將不屬于任何一方。

游戲開始，小涵和計(jì)算機(jī)要從自由武將中挑選武將組成自己的軍隊(duì)，規(guī)則如下：小涵先從自由武將中選出一個(gè)加入自己的軍隊(duì)，然后計(jì)算機(jī)也從自由武將中選出一個(gè)加入計(jì)算機(jī)方的軍隊(duì)。接下來一直按照“小涵→計(jì)算機(jī)→小涵→……”的順序選擇武將，直到所有的武將被雙方均分完。然后，程序自動(dòng)從雙方軍隊(duì)中各挑出一對(duì)默契值最高

的武將組合代表自己的軍隊(duì)進(jìn)行二對(duì)二比武，擁有更高默契值的一對(duì)武將組合獲勝，表示兩軍交戰(zhàn)，擁有獲勝武將組合的一方獲勝。

已知計(jì)算機(jī)一方選擇武將的原則是盡量破壞對(duì)手下一步將形成的最強(qiáng)組合，它采取的具體策略如下：任何時(shí)刻，輪到計(jì)算機(jī)挑選時(shí)，它會(huì)嘗試將對(duì)手軍隊(duì)中的每個(gè)武將與當(dāng)前每個(gè)自由武將進(jìn)行一一配對(duì)，找出所有配對(duì)中默契值最高的那對(duì)武將組合，并將該組合中的自由武將選入自己的軍隊(duì)。 下面舉例說明計(jì)算機(jī)的選將策略，例如，游戲中一共有 6 個(gè)武將，他們相互之間的默契值如下表所示：

洛谷 P1199 三國游戲

雙方選將過程如下所示：

洛谷 P1199 三國游戲

小涵想知道，如果計(jì)算機(jī)在一局游戲中始終堅(jiān)持上面這個(gè)策略，那么自己有沒有可能必

勝？如果有，在所有可能的勝利結(jié)局中，自己那對(duì)用于比武的武將組合的默契值最大是多

少？ 假設(shè)整個(gè)游戲過程中，對(duì)戰(zhàn)雙方任何時(shí)候均能看到自由武將隊(duì)中的武將和對(duì)方軍隊(duì)的武將。為了簡化問題，保證對(duì)于不同的武將組合，其默契值均不相同。

輸入輸出格式

輸入格式：

輸入文件名為 sanguo.in，共 N 行。

第一行為一個(gè)偶數(shù) N，表示武將的個(gè)數(shù)。

第 2 行到第 N 行里，第（i+1）行有（Ni）個(gè)非負(fù)整數(shù)，每兩個(gè)數(shù)之間用一個(gè)空格隔

開，表示 i 號(hào)武將和 i+1，i+2，……，N 號(hào)武將之間的默契值（0≤默契值≤1,000,000,000）。

輸出格式：

輸出文件 sanguo.out 共 1 或 2 行。

若對(duì)于給定的游戲輸入，存在可以讓小涵獲勝的選將順序，則輸出 1，并另起一行輸出

所有獲勝的情況中，小涵最終選出的武將組合的最大默契值。

如果不存在可以讓小涵獲勝的選將順序，則輸出 0。

輸入輸出樣例

輸入樣例#1：

【輸入樣例1】 6 5 28 16 29 27 23 3 20 1 8 32 26 33 11 12 【輸入樣例2】 8 42 24 10 29 27 12 58 31 8 16 26 80 6 25 3 36 11 5 33 20 17 13 15 77 9 4 50 19 輸出樣例#1：

【輸出樣例1】 1 32 【輸出樣例2】 1 77

分析：直接排序找第二大的就好了

代碼：

include

include

using namespace std;

int a[509][509]={0},n,b[509],f[509];

int main() { scanf(“%d”,&n); for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { scanf(“%d”,&a[i][j]); a[j][i]=a[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { b[j]=a[i][j]; } sort(b+1,b+n+1); f[i]=b[n-1]; } sort(f+1,f+n+1); PRintf(“1/n%d”,f[n]); return 0; }