超级分类无敌边界 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, 虽然解题方法不是最优, 但是思考了很多, 不看题解远比看题解要想得多, 训练程度高得多, 我喜欢这种感觉!

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

本文链接

今天的经历非常好玩

回复