超级分类无敌边界 PK 简单分类强悍贪心 @ CodeForces 478C 题解
三种颜色的气球分别有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. 这种方案的难点就是分类周全+边界考虑清楚. 代码如下:
/**
* I love coding
* @Author: Jecvay
*/
#include <iostream>
using namespace std;
inline int gint() {int n;scanf("%d", &n);return n;}
int dfs(int a, int b, int c) {
if (b < c) swap(b, c);
if (a < b) swap(a, b);
if (b < c) swap(b, c);
int z = 0;
if (a * b + a * c + b * c == 0) return 0;
if (a == b && b == c || (a - b <= 2 && b == c) || (a == b && a - c <= 2)) {
a -= c;
b -= c;
z = c;
c = 0;
if (z == 0) {
if (a == 2) return 1;
return 0;
}
z += dfs(a, b, c);
} else if (a == b && b-c >= 3) { // -3 -3 0 ---> 2
int x = (b-c+2) / 3;
x = min(x, b / 3);
a -= 3 * x;
b -= 3 * x;
z = 2 * x + dfs(a, b, c);
} else if (b == c && a-b >= 3) { // -4 -1 -1 ---> 2
int x = (a-b+2) / 3;
x = min(x, a/4);
x = min(x, b);
a -= 4 * x;
b -= x;
c -= x;
ast(a >= 0 && b >= 0 && c >= 0);
z = 2 * x + dfs(a, b, c);
} else {
if (a > 1 && b > 0) {
int x = min((a-c)/2, b-c);
x = min(x, a-b);
x = min(x, a/2);
x = min(x, b);
a -= 2 * x;
b -= x;
z = x + dfs(a, b, c);
}
}
return z;
}
void solve() {
int cnt = 0;
cout << dfs(a[0], a[1], a[2]) << endl;
}
int main() {
for (int i = 0; i < 3; i++)
a[i] = gint();
solve();
return 0;
}
既然 Accepted了, 就可以看看别人的代码怎么写的了, 不看不知道, 一看吓一跳, 代码如下:
int main() {
cin >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
cout<<min((a[0] + a[1] + a[2]) / 3, a[0] + a[1]);
}
两三行代码就搞定了. 这让我有点儿兴奋, 这是怎么做到的. 仔细想了一会, 原来是贪心策略就和我和原哥想的不一样. 这个贪心策略是这样的:
- 如果气球全用光了, 那么答案一定是所有气球的总数加起来除以三
- 如果气球没用光, 剩了一种颜色的气球A, 那么答案的个数则是其余两种气球个数之和 B + C, 原因就是每个桌子插两个A, 一个B, 或者两个A, 一个C, 这样耗到最后B和C都没了, 剩下A.
今天的经历非常好玩
我昨天有缘碰到这篇文章, 然后我就开窍了, 我感觉我做题再少都没问题, 但是不能再像以前一样依赖题解. 今天我尝试了一下, 自己思考得出了AC, 虽然解题方法不是最优, 但是思考了很多, 不看题解远比看题解要想得多, 训练程度高得多, 我喜欢这种感觉!
那种感觉就是, 题解不是写给不会做题的人看的, 是写给做出来题目的人看的, 用来在有了基础的情况下开阔眼界用的. 哎, 不过话是这么说, 世事难料, 不知道我能不看题解坚持做题到什么时候…