超级分类无敌边界 PK 简单分类强悍贪心 @ CodeForces 478C 题解

October 17, 2014 | 23:43

三种颜色的气球分别有R, G, B个, 每个桌子插三个气球, 每个桌子上的气球不能全是同一种颜色, 求能插多少个桌子.

这道题我在当时没写出来. 当时和原哥讨论, 首先是看错题以为是搜索, 后来看清题目后发现没那么复杂, 只需要贪心就可以. 然后我采用了原哥提出的这个贪心策略:

三种气球个数最多的减二, 次多的减一为一次操作. 能做多少次这样的操作, 答案就是多少次.

这是个正确的贪心策略, 我立马敲完代码交上去然后得到了 TLE. 这说明需要优化. 想到 A 题和 B 题都是用乘法优化加法, 难道今天是乘法优化专场, 于是我就想类似的用乘法优化. 这个想法引导我写了一个长长的程序, 把情况分为如下几类(假设 RGB 经过排序, R >= G >= B)

  • R == G == B
  • R == G > B
  • R > G == B
  • R > G > B

这样就有四个 (else) if 语句. 分类好了之后就是列出不等式, 计算乘法优化的那个乘数有多大. 这个过程耗费了我很多时间去 Debug, 修改不等式, 想特殊情况. 最后拿到了 Accepted. 这种方案的难点就是分类周全+边界考虑清楚. 代码如下:

 

既然 Accepted了, 就可以看看别人的代码怎么写的了, 不看不知道, 一看吓一跳, 代码如下:

两三行代码就搞定了. 这让我有点儿兴奋, 这是怎么做到的. 仔细想了一会, 原来是贪心策略就和我和原哥想的不一样. 这个贪心策略是这样的:

  • 如果气球全用光了, 那么答案一定是所有气球的总数加起来除以三
  • 如果气球没用光, 剩了一种颜色的气球A, 那么答案的个数则是其余两种气球个数之和 B + C, 原因就是每个桌子插两个A, 一个B, 或者两个A, 一个C, 这样耗到最后B和C都没了, 剩下A.

 

今天的经历非常好玩

我昨天有缘碰到这篇文章, 然后我就开窍了, 我感觉我做题再少都没问题, 但是不能再像以前一样依赖题解. 今天我尝试了一下, 自己思考得出了AC, 虽然解题方法不是最优, 但是思考了很多, 不看题解远比看题解要想得多, 训练程度高得多, 我喜欢这种感觉!

那种感觉就是, 题解不是写给不会做题的人看的, 是写给做出来题目的人看的, 用来在有了基础的情况下开阔眼界用的. 哎, 不过话是这么说, 世事难料, 不知道我能不看题解坚持做题到什么时候...

 

 

( 转载请注明: Jecvay Notes )

说几句