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();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

最后

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