1、BOI 2002 Tennis 解題摘要中文譯題乒乓球正在組織名為“有趣的一個乒乓球周”的活動，從而吸引新會員加入。他們已經(jīng)邀請了一些乒乓球來演示比賽，來吸引人們。每位已經(jīng)指明了他（她）愿意參加的比賽場數(shù)，組織者也希望給個運動員相遇超過一次。們一些樂趣，因此他們想策劃比賽表，使得沒有兩你的任務(wù)是寫一個程序幫助他們把運動員配成對，使得每個運動員參加的比賽場數(shù)恰為他的期望值，并且不與其他任何一名運動員交鋒兩次或己交手。當(dāng)然，沒有人會與他（她）自輸入數(shù)據(jù)輸入文件（tennis.in）的第一行是運動員人數(shù) N（2 = N = 1000），接下來的 N 行是每個運動員期望參加的比賽場數(shù) GI （1 =

2、GI D(C) （D 表示定點的度），正因為如此，一定至少有一個點 Z 滿足 Z 和 B 之間有邊但是與 C 卻沒有邊，這樣，將 A-C 邊改為 C-Z，B-Z 邊改為 A-B 仍然滿足條件，于是也滿足算法的要求，命題得證。最后，分析一下程序的時空復(fù)雜度。時間復(fù)雜度：O(N2logN)主要是排序的時間，若用歸并排序，可以降至 O(N2)。空間復(fù)雜度：O(N2)，可以降至O(N)。總結(jié)本題是一道較為簡單的構(gòu)造題（也可以說成是貪心），設(shè)計算法并不是什么難事，只要有縝密的思維，后面的證明也是水到渠成的事情。附錄程序11程序是時間復(fù)雜度為 O(N2logN)，空間復(fù)雜度為 O(N2)。程序12221

3、32121英文原題Tennis ClubThe Matchball tennis club isanizing a “gameerestk” to attract new players to the club.As one of the attractions, they have asked some star players to play a few demo games. Each starhas indicated the number of games he or she is willing to play. The have some fun as well, thus th

4、ey want to schedule the games son once with each other.anizers want the stars tot no two players meet moreYour task is to write a program to help them match the playerso pairs sot each playlayshis or her desired number of games and does not play twice or more against any othcourse, no player may pla

5、y against himself or herself.layer. OfInput dataOn theline of the input file tennis.in is the number of players N ( 2 = N = 1000 ) and on thefollowing N lines is the desired number of games to playGI (1 = N ) for each player.GIAmet the players are numbered from 1 to Nhe order of their wisheshe input

6、 file.Output dataOn theline of the output file tennis.out write NO SCHEDULE if it is notsible to create asible.schedule sot the wishes of all players are satisfied, or SCHEDULE if it isIf a schedule exists, write it out on the following N lines. On each line write the indiofopponents for player whose desired number of games was indicated on the corresponding inputline. On each line the indimust be in increasing order and separated by spa. If multiplesolutions exist, output any one of them.ExlesTennis.ennis.outTennis.ennis.out3SCHEDULE3NO SCHEDULE122Gradinghis task, a program