C. Color the Picture（贪心/构造）

题目

题意

给定n * m的矩阵，用k种染料去涂这些格子。每种燃料有a[i]个。 要求涂抹后的每个格子，它的相邻格子，至少有3个是相同颜色。 这里相邻格子的定义比较特殊。对于(x1,y1)和(x2,y2)，它们相邻，当且仅当满足以下其中之一。

比如对于下图，(1,2)的相邻格子是4个灰色结点。

思路

为了保证每个结点有3个同色的相邻结点，那么它至少有3个方向的格子是相同颜色的。 这意味着，我们构造的同色格子，要么是占据至少2行的，要么是占据至少2列的。 不失一般性，我们下面只讨论按列划分的情况。

问题转化为，给定m列，如果用k种燃料去填充每以列，使得每种燃料至少有填充2列以上。

• 为了尽量不浪费燃料，我们需要优先使用数量多的燃料。
• 为了能尽量利用每种燃料，我们需要尽量让每种燃料都用上。

为了满足第一条件，我们需要优先从数量大的燃料开始取； 为了满足第二条件，我们需要每种燃料都只取2列，多余的再额外记录下。

详见代码res和left变量。

代码

#include  using namespace std; #define ll long long #define inf 0x3f3f3f3f const int maxn = 200010; int n, m, k; ll a[maxn]; void solve() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= k; ++i) { scanf("%lld", &a[i]); } sort(a + 1, a + k + 1);// sort  bool ok = false; // 1. color every col ll res = 0, left = 0; for (int i = k; i >= 1; --i) { ll tmp = a[i] / n; tmp = min(tmp, m - res);// 这里是防止剩余的列数不够  if (tmp <= 1) { continue; } res += 2; left += tmp - 2;// 多的染料存在left 备用  } ok |= (res + left) >= m; // 2. color every row res = 0;left = 0; for (int i = k; i >= 1; --i) { ll tmp = a[i] / m; tmp = min(tmp, n - res); if (tmp <= 1) { continue; } res += 2; left += tmp - 2; } ok |= (res + left) >= n; printf("%s\n", ok ? "YES" : "NO"); } int main() { int t; scanf("%d", &t); //	t = 1; while (t--) { solve(); } } 

最后

weixin gongzhonghao搜 对方正在debug，关注下，一起快乐刷题吧~