开个帖子记录自己刷挑战程序竞赛的历程

14417335 发表于 2019-2-12 05:26
"上网搜索了一番之后我觉得这本书还是挺好的" 是哪本书？

挑战程序设计竞赛 https://book.douban.com/subject/24749842/

必须跟着楼主跑，楼主好样的，加油，支持你这种有毅力、有想法的

2011051305 发表于 2019-2-11 09:20
C++ or Java ?

C++ 。。。。。。。。。。。。。。。。

楼主6666，我以前刷了三章刷不下去了

fleetfei 发表于 2019-2-13 00:38
必须跟着楼主跑，楼主好样的，加油，支持你这种有毅力、有想法的

多谢鼓励！才刚刚开始。。

huzihao46 发表于 2019-2-13 06:43
楼主6666，我以前刷了三章刷不下去了

三章已经很碉了。。。我只打算把第二章精刷，后面的选刷了。。

贪心的部分挑战程序设计竞赛上内容不多，我又从别的地方找了一些资料，一并加上。

2.2 贪心法

和动态规划和穷竭搜索不同，贪心法的主要特征是遵循某种规则并且贪心的选组当前最优策略。通常利用贪心的例子解决的问题有：

(A) 背包问题

例题1: 给1，5，10，50，100，500 元的硬币各若干枚，支付A元，最少需要多少硬币，假设至少存在一种支付方案。

这题可以采取简单的贪心策略来解决－也就是先尽量优先使用大面值的硬币。但是注意这里贪心成立的条件是每个小面值的硬币一定可以被大面值的硬币给整除。例如反例 1 6 11 15, 面值20就显然不能用贪心来解决。

例题2： n个物体，第i个物体重量位wi, 价值位vi, 每个物体都可以只取走一部分。总重量不超过c的情况下求最大的总价值。

每个物体可以只取走一部分，因此要么我们刚好取满c重量，要么取走全部物品。因此这里可以简单的用贪心解决-我们尽可能取单位价值大的物品即可。

(B) 区间问题

这个又可以细分为三类

区间相交问题： N个区间，选择最多的区间使其各不相交

贪心策略：根据区间结束时间排序，优先选取结束时间早的。直觉上理解，显然这样可以保证多取区间。

区间选点问题： N个区间，取尽量少的点，使得每个区间至少都包含一个点

贪心策略：同样根据区间结束时间排序，如果结束时间相同根据区间开始时间排序。对每个区间 X, 如果没有已经被包含，则选择最右端的点。直觉上来说，尽量将该点右移动首先不会造成更坏的结果（不会导致错过其他区间，因为所有其他还未处理的的区间都在 X 以后结束），同时可以保证尽量该点可以覆盖更可能多的区间。

区间覆盖问题：N个区间，选择尽量少的区间覆盖指定线段 [s, t]

贪心策略：遍历每个点，如果某点还没覆盖，当然是选择结束时间最晚的区间覆盖。具体做法是将区间根据开始时间排序，如果第一个区间的起点不能覆盖s,无解。否则选择起点包含s的结束时间最晚的区间 X。假设 X 结束时间是 ti, 则下面直接跳到 ti 重新上述过程。虽然看上去复杂，但是因为还是只需要一次扫描，因此复杂度还是 O(NlogN + N) (排序+1次遍历）

(C) 霍夫曼编码问题

给n个字符的频率ci, 给每个字符赋一个01编码串，使得任意一个字符的编码不是另外一个字符编码前缀，并且编码总长度（字符频率 * 编码长度)最小.

贪心策略：构建01二叉树，每个叶子节点都对应一个字符，从root到该叶子的0,1序列即为该叶子的编码。为了保证出现频率大的字符尽量编码长度短，我们应该让其的深度尽量小，反之则反。因此贪心策略是把每个字符看做单叶子子树放在集合中，权值等于字符频率，每次取权值最小的两个子树组成新树并且重新放到集合中，新树的权值等于两个子树的权值之和。具体实现可以用优先队列。

例题：

POJ 3617：Best Cow Line

给一个字符串，每次从头取一个或者从后面取一个，最后组成一个新的字符串。问用这种套路能取出来的字典序最小的字符串。

思路：贪心水题。可以按位比较输入字符串 S 以及 S[::-1], 哪个小就取那个。如果S[ i] == S[j],直接比较字典序 S[i:] 和 S[j:] 即可。实际 implement 无需构造字符串，双指针即可。

POJ 3069: Saruman's Army

给一列数A，每个元素代表军队里的军人位置，再给一个武器的攻击范围值K.在某点i放置武器可以覆盖 [A[ i] - K, A[ i] + K]的所有数，求最少的武器个数可以覆盖所有军队。

思路：lc上有类似的题目。贪心的策略很容易想到：尽可能的把武器往右放。但是这题写起来想要做到简单clean还是有点麻烦。我采取的做法是首先研究第一个武器最远能放在哪里，然后再写一个循环寻找下一个必须要放武器的地点，如此循环。这样要写两个while loop, 不过逻辑简单而且能处理所有的corner case.

POJ 3253: Fence Repair

一块木板要切成N块，每块大小已经确定，每次把长度为 L 的木板切开所用代价为 L, 求最小代价的木板切割方式

思路：我们可以画树来表示切割的过程，然后发现为了保证总代价最小，越短的木板在树中的深度越大。因此把木板长度对应成单词频率，这题和霍夫曼编码其实一模一样。

POJ 2376: Cleaning Shifts

N个奶牛，每个奶牛可以做一些时间段的工作，求最少奶牛数量可以保证T段时间的工作都有奶牛可以做。

思路：区间覆盖标准模板题。但是注意这里时间段的概念。比如奶牛A的输入是1 7, 这意味着该奶牛可以覆盖时间 1 - 8.　因为没仔细读例题的我因为损失惨重（时间），一直 WA...

POJ 1328: Radar Installation

平面区域上分布着N个小岛。现在在x轴上放置雷达，每个雷达的侦测范围是D,求最少雷达个数可以覆盖所有小岛，如果不能覆盖，输出－１

思路：一开始看到这题觉得很简单，先从最左边的小岛开始，尽量在该小岛右边防止雷达，最远距离位 x + sqrt(D*D - y*y).这样可以保证覆盖最多的小岛。然后遍历一下即可。

不幸这种思路是错误的，结果就是我一直 wa 了四个小时。。。这里的关键在于设计贪心策略的时候一定要认真考虑是否正确。我一拍脑袋想到的尽可能在小岛右边最远的地方放置雷达的策略是错误的！简单的例子：小岛 A 位置 （-1, 1），小岛 B 位置 (0, 2), 雷达范围是２。那么其实在 (0, 0)点处放置一个雷达即可。如果按照以上的贪心策略，则会在 (sqrt(2), 0)处放置一个雷达，which 是不能覆盖 (0, 2)的！！

正确思路是反向而行之，以每个小岛为圆心，半径为D画圆。那么 [x - sqrt(D*D - y*y), x + sqrt(D*D + y*y)]　内所有放置的雷达显然都是可以覆盖到该岛的，于是问题就被转化成了区间选点问题。

POJ 3190: Stall Reservations

N个奶牛，每个都只能在某区间时间段内产奶，并且每个奶牛只能独自在某围栏内产奶，问最少需要多少围栏，以及围栏的分配方式。

思路：想当年我dream company正是挂在这道题上，真是仇人相见分外眼红。这题其实是 LC meeting room 升级版，不仅需 meeting room 数量也需要 meeting room 的具体分配。具体的思路是这样的，我们首先现将区间按照起点排序，然后把每个区间的结束时间都扔到 priority queue 里。这样每次新开始一个区间的时候，我们检查结束最早的（在 priority queue)的区间所占据的围栏x是不是已经空出来了，如果是，则新的区间就用x。 否则，我们需要给新的区间新分配一个围栏。我们用cnt来记住当前已经分配的围栏的最大编号，最后cnt的值即是最少需要的围栏个数。

要点：
1. 如果只问需要的围栏个数，不需要具体分配，扫描线即可解决
2. 有个问题是最后的结果需要按照输入顺序输出，但是经过排序以后我们的输入已经被打乱，具体做法是首先给每个输入的奶牛产奶区间编号，然后根据该编号来确定最后的输出位置。据说这是一种常用的trick.

开始找到了一点刚开始刷leetcode时候的感觉，各种不会。。看到题目各种懵逼，看完答案深深为自己智商感到绝望。。
POJ 2393: Yogurt factory

N周，每周需要生产Ai unit的奶酪，每周的生产成本为 Ci, 注意价格会上下浮动。多生产的奶酪可以存储，存储费用为 S, 求总的最少生产费用

思路：很显然，第j周的奶酪的最小生产费用是 Cj + (j-i)*S, for all i <= j. 看上去似乎我们需要写一个 O(N^2)　的算法来解决，不过仔细考虑，设第i周的最小生产费用是 min_price, 不管这个min_price是怎么来的，那么第i+1周的最小生产费用肯定是 min(min_price + S, C[i+1]), 因此只要不停更新最小生产费用就可以做到 O(N) 时间 O(1) 空间了。

要点:
1. 如果第j天的情况依赖于1 -> j-1天的情况，下意识的想到可否把前面的计算结果保存下来，免得重复计算
2. 这题已经提示了说结果可能 int 装不下，仔细看题目啊！！

POJ 1017: Packets

一共有６种大小的正方形瓷砖，边长从1到６。分别给出这６种瓷砖的数量。工厂要把他们装在 6*6 的包装袋中。问最少需要的包装袋数、

思路做这题的时候感受到了智商天花板。很明显这题应该先放边长是6,5,4,3的，剩下的看看还需要多少包装袋放2,1。但是我只会从正面去考虑这个问题，也就是想装4的包装袋还能装多少2, 然后完了还剩下多少2, 然后再考虑装３的包装袋。。太愚蠢了！

实际的做法是直接计算4,3可以装多少２，然后比较一下看看是否还需要更多的包装袋来装２．然后下面是不是还需要遍历各种条件来看看能否装１呢？不用！直接计算剩下来的面积就可以！(共计包装袋数量 * 36 - cnt_6 * 36 - cnt_5 * 25...)

POJ 3040: Allowance

农夫有N种硬币，每种硬币都有相应的个数和币值。需要用这些硬币去付款，每周需要最少付款C元，求最多付款周数

思路：好难。。。想了N个小时最后还是看的题解。。看了好久才看懂。贪心的策略很快就能想到就是先从大往小取，可是我一直没想清楚的是如果不能刚好凑满C元的处理方法。后来看了答案才发现解题核心是由两个贪心策略构成的：
1- 首先从大到小取硬币，但是不能超，这样保证我们尽快接近C
2- 如果还有剩余的，这意味着我们任意再取一枚硬币就会超了(想一想为什么?)，这种情况下我们为了避免浪费取最小的
3- 重复以上过程，直到步骤２结束后剩余硬币价值依然 > 0

还有一个精妙的优化，就是1, 2完后我们记录下每种硬币的需要的个数 cnt, 最后我们可以直接用 min(coins_value[ i ] / cnt[ i ])来计算相同的取法有多少种(例如题目给的例子，5, 1的取法可以取100种，我们一次遍历就够了）。

POJ 1862: Stripies

N个微生物，两两结合后体重会变成 sqrt(m1*m2), 求最后结合完的最小体重

思路：做完上面那题再做这题简直如沐春风。越先结合的sqrt的次数越多，因此显然应该尽量先结合大的微生物。纯粹的模板题目。虽然很快敲完了但是也没什么思考的快感了。。

POJ 3262: Protecting the flowers

N个奶牛，每个奶牛带回去时间来回需要Ti, 每个奶牛单位时间内摧毁Di朵花, 决定奶牛带回顺序使得被摧毁的花的总数最小。

思路:　在需要决定整体顺序的时候，我们只两两考虑。面对奶牛i和奶牛j，怎么决定先带回哪一个呢？这取决于Ti*Dj以及Tj*Di的大小。因此我们根据这个compare rule对整个奶牛进行排序，然后挨个带回去就好了。

一种比较naive的思路是先带破坏力高的奶牛，稍加思考可发现这个思路是不对的。比如 (1, 1), (4, 2), 先带奶牛２导致总共有４朵花被破坏，反之则只有１个。通过这个例子我们也应该能领悟到这题排序的准则。

感谢楼主分享！

看到Github上有个repo ： https://github.com/yogykwan/acm-challenge-workbook

不过好像都没找到Java相关的解答..都是C++的