集训队作业tennis解题报告

1、BOI 2002 Tennis 解题摘要中文译题乒乓球正在组织名为“有趣的一个乒乓球周”的活动，从而吸引新会员加入。他们已经邀请了一些乒乓球来演示比赛，来吸引人们。每位已经指明了他（她）愿意参加的比赛场数，组织者也希望给个运动员相遇超过一次。们一些乐趣，因此他们想策划比赛表，使得没有两你的任务是写一个程序帮助他们把运动员配成对，使得每个运动员参加的比赛场数恰为他的期望值，并且不与其他任何一名运动员交锋两次或己交手。当然，没有人会与他（她）自输入数据输入文件（tennis.in）的第一行是运动员人数 N（2 = N = 1000），接下来的 N 行是每个运动员期望参加的比赛场数 GI （1 =

2、GI D(C) （D 表示定点的度），正因为如此，一定至少有一个点 Z 满足 Z 和 B 之间有边但是与 C 却没有边，这样，将 A-C 边改为 C-Z，B-Z 边改为 A-B 仍然满足条件，于是也满足算法的要求，命题得证。最后，分析一下程序的时空复杂度。时间复杂度：O(N2logN)主要是排序的时间，若用归并排序，可以降至 O(N2)。空间复杂度：O(N2)，可以降至O(N)。总结本题是一道较为简单的构造题（也可以说成是贪心），设计算法并不是什么难事，只要有缜密的思维，后面的证明也是水到渠成的事情。附录程序11程序是时间复杂度为 O(N2logN)，空间复杂度为 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