C++信奥教学PPT：CSP_J_算法之贪心算法

餐厅评级（Restaurant Ratings, North America-Rocky Mountain 2014,LA6872）旅行网站设计了一个餐馆评级系统，每个餐馆都由n（1≤n≤15）个评论家来打分，每人打一个正整数的分数（越高越好）。餐馆的排名规则是先按照各个评论家的打分总分（不超过30）排序。如果总分相同，就按照1～n这n个评论家的n个打分的字典序排序。现在给出一个餐馆的得分，计算按照以上排名规则，排名不超过这个得分的所有可能的打分结果的个数。输出保证可用64位有符号整数存放。

锁着的宝藏（Locked Treasure, North America-Rocky Mountain 2014,LA6873）有n（1≤n≤30）个强盗把宝藏锁在一屋内，必须至少有m（1≤m≤n）个一致同意才能去取宝藏。他们在门上放很多锁，必须同时打开才能开门。每个锁可以配不超过n把钥匙，分别发给一些强盗。一组强盗当且仅当其中有人有这把锁的钥匙时才能打开这把锁。给出n和m，计算最少需要多少把锁才能保证：在钥匙分配合理的前提下，任何组强盗只有在人数不少于m的情况下才能打开锁宝藏的门。举例来说，如果n＝3，m＝2，需要3把锁就行了。锁1的钥匙给强盗1和2，锁2的钥匙给强盗1和3，锁3的钥匙给强盗2和3。没有一个强盗能独自打开锁，但是任何两个强盗组成一组就可以打开所有的锁。需要思考一下为什么2把锁不能满足条件。

人名追踪（What's In A Name？，North America-East Central NA 2001，LA2354）FBI正在监控一个犯罪窝点，里面有n（n≤20）个嫌疑人，都有唯一ID。FBI记录了一系列按照时间顺序排列的人员进出（使用人名）的情况，以及窝点向外发送消息的记录（使用ID）。所有的ID以及人名都会在记录中出现，一开始窝点是空的。所有的人名和ID都只包含最多20个小写字母。根据这些记录计算出ID和人名的对应关系，按照人名的字典序输出。如果根据记录无法确定一个人名对应的ID，就输出“？？？”作为ID。

字母排序（Sorting It All Out，North America-East Central NA 2001，LA2355）对于前n个大写字母（2≤n≤26），输入m个形如A＜B的关系，表示字母A排在B前面。根据输入顺序对n个大写字母按照上文给定的顺序排序并且输出结果。如果无法确定顺序或者给定的m个关系互相矛盾，也输出相应的结果（具体输出格式请参考原文）。