D. Grid Puzzle
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
You are given an array \(a\) of size \(n\).
There is an \(n \times n\) grid. In the \(i\)-th row, the first \(a_i\) cells are black and the other cells are white. In other words, note \((i,j)\) as the cell in the \(i\)-th row and \(j\)-th column, cells \((i,1), (i,2), \ldots, (i,a_i)\) are black, and cells \((i,a_i+1), \ldots, (i,n)\) are white.
You can do the following operations any number of times in any order:
- Dye a \(2 \times 2\) subgrid white;
- Dye a whole row white. Note you can not dye a whole column white.
Find the minimum number of operations to dye all cells white.
给你一个大小为 \(n\) 的数组 \(a\) 。
其中有一个 \(n \times n\) 网格。在第 \(i\) 行中，第一个 \(a_i\) 单元格为黑色，其他单元格为白色。换句话说，注意\((i,j)\)是第 \(i\) 行和第 \(j\) 列中的单元格， \((i,1), (i,2), \ldots, (i,a_i)\) 单元格是黑色的， \((i,a_{i+1}), \ldots, (i,n)\) 单元格是白色的。
您可以按照任意顺序多次进行以下操作：
- 将一个 \(2 \times 2\) 子网格染成白色；
- 将整行染白。注意不能将整列染白。
找出将所有单元格染白的最少操作次数。
Input
The first line contains an integer \(t\) (\(1 \leq t \leq 10^4\)) — the number of test cases.
For each test case:
- The first line contains an integer \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) — the size of the array \(a\).
- The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq n\)).
It's guaranteed that the sum of \(n\) over all test cases will not exceed \(2 \cdot 10^5\).
输入
第一行包含一个整数 \(t\) （ \(1 \leq t \leq 10^4\) ）。( \(1 \leq t \leq 10^4\) ) - 测试用例的数量。
对于每个测试用例
- 第一行包含一个整数 \(n\) ( \(1 \leq n \leq 2 \cdot 10^5\) ) - 数组的大小 \(a\) 。
- 第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\) ( \(0 \leq a_i \leq n\) )。
保证所有测试用例中 \(n\) 的总和不超过 \(2 \cdot 10^5\) 。
Output
For each test case, output a single integer — the minimum number of operations to dye all cells white.
输出
对于每个测试用例，输出一个整数 —— 将所有单元格染白的最少操作次数。
Example
input
10
1
0
4
2 4 4 2
4
3 2 1 0
3
0 3 0
3
0 1 3
3
3 1 0
4
3 1 0 3
4
0 2 2 2
6
1 3 4 2 0 4
8
2 2 5 2 3 4 2 4
output
0
3
2
1
2
2
3
2
4
6
Note
In the first test case, you don't need to do any operation.
In the second test case, you can do:
- Dye \((1,1), (1,2), (2,1)\), and \((2,2)\) white;
- Dye \((2,3), (2,4), (3,3)\), and \((3,4)\) white;
- Dye \((3,1), (3,2), (4,1)\), and \((4,2)\) white.
It can be proven \(3\) is the minimum number of operations.
In the third test case, you can do:
- Dye the first row white;
- Dye \((2,1), (2,2), (3,1)\), and \((3,2)\) white.
It can be proven \(2\) is the minimum number of operations.
注
在第一个测试案例中，您不需要进行任何操作。
在第二个测试用例中，您可以进行以下操作：
- 染 \((1,1), (1,2), (2,1)\) 和 \((2,2)\) 白色；
- 染 \((2,3), (2,4), (3,3)\) 和 \((3,4)\) 白色；
- 染 \((3,1), (3,2), (4,1)\) 和 \((4,2)\) 白色。
可以证明 \(3\) 是最少的运算次数。
在第三个测试案例中，你可以这样做：
- 将第一行染成白色；
- 将 \((2,1), (2,2), (3,1)\) 和 \((3,2)\) 染成白色。
可以证明 \(2\) 是最少的操作数。
我的题解
提示！以下文字仅代表我的想法
如果有更优的做法欢迎交流讨论
这题是很典型的贪心吧
首先，如果满足消除 \(2 \times 2\)块步骤较少的情况，那么这一行的黑块一定不超过 \(4\) 。因此，我们可以把黑色块数大于 \(4\) 的行处理成 \(4\) 并增加消除步数。（预处理）
其次，我们来处理剩下的块
假设全部用 \(2 \times 2\) 块的消除方法
我们先用一个变量 \(m\) 存储到第 \(i\) 行时连续用了多少次
再用一个变量 \(last\) 存储上一行的黑块数量
全部初始化为 \(0\)
我们对第 \(i\) 行黑块数量 \(a_i\) 进行分类讨论
- \(a_i = 0\)
- 假如 \(mem\) 不为 \(0\)，也就是说前面用的是 \(2 \times 2\) 块的消除方法，那就要判断前面的消除方法能不能正好全部消除前面的黑块（我们只用判断最后一个就可以了）
- 假如上一块的黑块数量是 \(4\)，那么是无论如何都不能完全消除的，所以要再用一次消除整行的方法把上一行清除（想知道为什么看上图消除方法）
- 假如上一块的黑块数量是 \(2\)，判断 \(mem\) 是奇数还是偶数：如果是奇数，那就可以完美消除，要减去 \(1\) 再加到 \(sum\) 里面，但是 \(mem - 1\) 不能小于 \(1\)；如果是偶数，就不是完美消除，不需要减 \(1\) 。（想知道为什么看上图消除方法）
- 如果 \(mem\) 为 \(0\) ，continue就好了。
- 假如 \(mem\) 不为 \(0\)，也就是说前面用的是 \(2 \times 2\) 块的消除方法，那就要判断前面的消除方法能不能正好全部消除前面的黑块（我们只用判断最后一个就可以了）
- \(0 \lt a_i \le 2\)
-
假如 \(mem\) 为 \(0\)，直接 \(mem\)++ 就好了。
-
假如 \(mem\) 不为 \(0\) ，看下一步能不能消除到这一行，也就是判断 \(mem\) 是奇数还是偶数
-
假如 \(mem\) 是奇数 ，那么下一个 \(mem\) 是偶数，那就不能覆盖这一个行，因此把前面的 \(mem\) 加到 \(sum\) 里面去再加 \(1\)，然后 \(mem\) 从该行重新开始计算（或者说给前面一块（一定是大于2的）用一次消除一整行的操作，把没有消除的消除掉。如下图，我认为第二种是比第一种更贪的，因为下一块的黑块有可能不大于2->浪费掉了）
-
假如 \(mem\) 是偶数 ，那么下一个 \(mem\) 是奇数，前面一块刚好完美消除掉黑块，因此可以直接接着算（虽然我是重新计算然后 \(mem = 1\) 的，但是大差不差）
-
-
- \(2 \lt a_i \le 4\)
- 假如 \(mem\) 等于 \(0\) 的话，不足以实现 \(2 \times 2\) 块的消除方法，因此直接用消除一整行的方法，\(sum\) ++。
- 假如 \(mem\) 不等于 \(0\)，直接 \(mem\) ++就可以了
退出循环后再处理一下mem就好了。
我的代码
#include <bits/stdc++.h>
#define int long long
const int N = 1e7 + 10;
int t;
int a[N];
void solve() {
int sum = 0;
int mem = 0;
int last = 0;
int n;
std::cin >> n;
for(int i = 0 ; i < n ; i ++) {
std::cin >> a[i];
if(a[i] > 4) {
sum ++;
a[i] = 0;
}
}
for(int i = 0 ; i < n ; i ++) {
if(a[i] == 0) {
if(mem) {
if(last <= 2 && mem & 1) sum += std::max(mem -1,(int)1);
else sum += mem;
}
mem = 0;
}
else if(a[i] <= 2) {
if(mem) {
sum += mem;
mem = (mem & 1 ? 0 : 1);
}
else mem ++;
}
else {
if(mem) mem ++;
else sum ++;
}
last = a[i];
}
if(mem) {
if(last > 2 || !(mem & 1)) sum += mem;
else sum += std::max(mem - 1,(int)1);
}
std::cout << sum << "\n";
}
signed main() {
std::cin >> t;
while(t--) {
solve();
}
return 0;
}