算法问题实战策略——1.2　程序设计竞赛

参加程序设计竞赛是培养解决问题能力的最佳途径。在目前各式各样的程序设计竞赛当中，本书选取设计要求较少、有运算时间限制、比拼快速设计能力的竞赛。此处的设计要求不同于实际开发中的要求，而是以“读入某个值，然后计算出某个值”的形式给出。 下面针对未接触过程序设计竞赛的读者举个简单的示例。 题目：摇滚音乐节（难度：低，题目ID：FESTIVAL） 要租用一个大的演出场地举办摇滚音乐节。这次音乐节将持续数日，每天有一支乐队举行演唱会。还未确定共邀请几个乐队，但已经与L个明星乐队交涉完毕，所以音乐节至少要举办L日。 要使用的演出场地每日租金各不相同，因此要妥当安排演出日程来节约成本。假设已经知道今后N日内的租金价格，在此期间连续租用L日，那么要使日均租金降至最低，应该怎样租呢？ 假设未来六天的租金为{3,1,2,3,1,2}，已邀请了3支乐队，那么举办4天音乐节要比举办3天日均租金更低。因为举办3天的最低日均租金是从第二天开始租用到第四天，租金为(1+2+3)/3=2；而从第二天开始一直租用到第五天的日均租金却只有(1+2+3+1)/4=7/4。 运行时间及占用内存的限制条件 程序运算时间限定为2秒以内，占用内存不得超过64MB。 输入 执行程序时，首先要求输入测试用例的个数C（C≤100），接下来的测试用例阶段第一行输入可租赁演出场地的最大天数N（1≤N≤1000），以及已邀请到的乐队数量L（1≤L≤1000，L≤N），然后在第二行输入N个日租金数。租金数为小于100的自然数。 输出 对应各测试用例，每一行显示一个最小日均租金数，允许小于107的绝对/相对误差。 输入示例 2 6 3 1 2 3 1 2 3 6 2 1 2 3 1 2 3 输出示例 1.7500000000 1.5000000000 从程序设计竞赛中学到的 程序设计竞赛的题目不同于实际开发过程中的规范，通过分析两者的不同，能得出竞赛题目具有以下优势。 1. 程序设计竞赛中设计的程序绝对不会使用图形界面，只利用文本方式进行输入、输出等操作。少了这些累赘，参赛者就可以集中所有精力去解决问题。 2. 对运算时间和内存使用量有明确限制。在测评运行时，如果参赛者提交的程序超时或内存使用量超出限制，则无论计算结果是否正确，都将视为错误答案。程序设计竞赛的题目都是需要集中计算 的，若不使用适当的算法和数据结构，就不可能设计出在限定时间内完成运算的程序。因此，参赛者需慎重选择要使用的算法，才能设计出满足限制条件的程序。对参赛者来说，程序设计竞赛是对丰富的算法设计技巧和数据结构进行实战的很好契机。竞赛提出的题目有些可以直接利用已知的算法解答，但还有些是必须在理解算法的原理后，再加以变换才能解答的题目。这对深刻理解其主题有着莫大的帮助。 3. 明确区分答案正确与否。实际开发中，通过单元测试或相互代码审查以测试代码的正确性。这种方法最多利用一两个输入的值测试程序代码。而程序设计竞赛利用多种多样的输入值测试运算的准确性，所以发生漏检错误的可能性较小。而且大部分的程序设计竞赛在赛后会立刻公布解题正误，甚至在有些竞赛中，参赛者提交解题代码后就能当场得知结果。自己编写的代码能够得到快速、客观的意见反馈，这无疑是编写高质量程序的很好锻炼。 4. 提交程序后，运算时间和内存使用状况等信息会实时提供给参赛者。因此，可以一边修改自己的程序代码，一边观察修改对程序效率产生的影响。这种方式能够提高对逻辑结构复杂的程序进行性能预测的能力，对实际工作当中编写高性能程序有很大帮助。 5. 程序设计竞赛的程序规模都比较小，所以每个题目都要从头开始编写。这种特性使参赛者有机会认真研究开发大型项目时忽视的小细节。开发大项目时无法随意更改代码结构，有时还会为了整体性能而牺牲程序的优雅之感。但编写竞赛的小型代码时不用考虑这些问题，能够投入更多时间编写优雅的程序，成为编写出好代码的极佳练习。 6. 程序设计竞赛中，参赛者在多人竞争的环境下编写代码。从某种意义上讲，相互竞争是提高自身实力的一个动机。还值得注意的是，许多竞赛结束后会公开所有参赛者的源代码。实际开发中，不会有两个或两个以上的程序员同时编写相同功能的代码。但在竞赛中，所有参赛者均同时编写相同功能的代码。因此，参赛者有机会把自己编写的代码与世界顶尖程序员编写的代码进行比较，从而进一步提升自己的能力。 这些特点使得程序设计竞赛强调解决问题的能力，因此，竞赛中只保留必备要素，舍弃其他无关紧要的部分。所以，程序设计竞赛是学习解决问题的最佳环境。 各位是否也感到值得一试呢？