国家集训队作业coins解题报告.pdfVIP

《Coins》解题报告 仇荣琦 【题目来源】 Baltic Olympiad in Informatics 2006 【题目描述】 有一个 ，流通着N种面值的硬币，其中包括了1分硬币。另外，有一种面 值为K分的 ，它超过了所有硬币的面值。有一位硬币收藏家，他想收集每一 种面值的硬币样本。他家里已经有一些硬币，但是现在他只带着一张K分 去 商店。商店里总共有K-1种商品，价格分别为1分、2分……K-1分。这家商店使 用以下算法找零： 1、假设总共需要找A分； 2、寻找最高的不超过A的硬币面值，设它为B分硬币； 3、给顾客一枚B分硬币，然后令AA-B； 4、如果A=0，算法结束；否则转2。 收藏家想用他的K分 买一件商品。请你编写程序，计算： ⚫ 收藏家能够得到多少种他还没有过的硬币？ ⚫ 在满足上一问的前提下，他能够买的最贵的商品是什么？ 【输入格式】 第一行为两个整数N (1≤N≤500000)和K (2≤K≤1000000000)。 以下N行描述流通的硬币。第i+1行包含两个整数ci(1≤ciK)和di，其中 ci表示第i枚硬币的面值；di=1表示收藏家已经拥有了这枚硬币，di=0表示他 还没有。硬币是以面值升序给出的，即c1c2…cn。另外，第一枚硬币一定是 1分，即c1=1。 【输出格式】 第一行为一个整数，表示收藏家最多能获得多少种之前还没有的硬币。 第二行为一个整数，表示在前一问的前提下，收藏家能 的最贵的商品价 格。 【输入样例】 7 25 1 0 2 0 3 0 【输出样例】 3 6 【题目分析】 题目的大意是：一位收藏家用一张K 分的 去买小于K 分的任意商品。商 店有N 种硬币，找零时使用的是贪心算法——尽量选大面值。求最多能够得到的 之前没有的硬币种数。 首先分析简单的情况：收藏家一种硬币都没有。也就是说，所有的硬币都是 需要的。 考虑找零总数为A 的某种找零方案（不一定是商店采用的方案），设S 表示 i c ,c ,…,c 在方案中出现的硬币总价值。我们可以得出以下的结论： 1 2 i 某种找零方案是商店采用的方案当且仅当S c (1≤iN)且S K。 i i+1 N 证明：命题的充分性是显然的，关键是证明必要性。易知S 是单调不减的， i 即 S ≤S ≤…≤S 。假设找零方案中总共出现了 tot 种硬币，分别为 1 2 N c c , a1 ,ca2 ,  atot 。考虑商店 找零算法 第一次选硬币的过程 ，有 tot K = cai = Satot  catot +1 ，而K = Satot  catot ，所以商店一定会选择硬币 i=1 ca ，即该方案中的第 tot 枚硬币与商店的选择相同。假设商店找零算法前 tot i-1次选出的硬币分别为catot , catot −1 ,, catot −i +2 ，那么商店在第i次选硬币时， tot =−  A A c S c i