SGOI5《足球赛》解题报告

大榕树 \ 信息学奥赛 \ 解题报告

SGOI5《足球赛》解题报告

原文链接：http://www.mydrs.org/program/list.asp?id=252
一、题意简述

　　有5支球队，已知比赛的成绩总积分，进球数与失球数，并且假设一支球队一场比赛最多进5球，求一种可能的比分方案。
二、算法分析

　　由于只有5支球队，并且还是单循环赛，所以很容易想到用搜索来做这道题。由于规模很小，我们可以一场一场的搜，也可以一支队一支队的搜，都可以在题目限定的时间内出解。
　　当然，为了精益求精，我们还可以加一些剪枝 , 以提高搜索效率。
　　1．根据5支球队实际总得分，可以算出平局的总场数，减少搜索量。
　　　　　　平局总场数＝3×比赛总场数－各球队得分之和。
　　2．对于每支球队的实际得分，可以算出该队至少赢了几场球。
　　　　　　至少赢球场数＝(该队得分－该队比赛场数＋1) div 2；
　　以上数据是搜索前就可以算出的。
　　在搜索过程中,还应注意以下几点:
　　　　1．如果剩余场次*最大进球数<剩余进球，则回溯。
　　　　2．如果最大剩余得分<实际剩余得分，则回溯。
　　此外还有一些剪枝 , 这里就不一一列举了。

三、小结

　　这是一道饶有趣味的题目，有很灵活的搜索方式与众多的优化手段。若增加题目的规模，不同程序的运行效率就会有明显的差别。大家可以尝试不同的编法，以找出一种最高效的方法。

作者：
来源：福州一中
时间：2001-10-17

上一篇：SGOI5《彩虹7号》解题报告
下一篇：SGOI5《控制棋》解题报告