526互联

codeforces 1804D Accommodation

发布时间 2023-04-07 23:00:36作者: 冯文健

https://codeforces.com/problemset/problem/1804/D

解题思路

每个楼层是独立的，考虑怎么解决一层就可以了。

求最大值就是尽量避免1和1合并，也就是尽量在不存在连续1的子序列中进行合并，如果还有需要合并的就只能用1和1合并。求最小值就是尽量合并1和1。由于只需要输出最大最小值，所以遍历序列用贪心求解就行了。

/* https://codeforces.com/contest/1804/problem/D */
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, pre, num[2], sum, tmp[2], cnt, Max, Min;

    while (scanf("%d %d", &n, &m) != EOF) {
        Max = Min = 0;
        for (int i = 0; i < n; i++) {
            pre = -1;
            num[0] = num[1] = 0;
            sum = tmp[0] = tmp[1] = 0;
            for (int j = 0; j < m; j++) {
                char c = getchar();
                if (c == '\n') {
                    j--;
                    continue;
                }

                cnt = c == '0' ? 0 : 1;
                sum += cnt;

                if (num[0] == 0) {
                    pre = cnt;
                    num[0]++;
                } else {
                    if (cnt == 0) {
                        pre = cnt;
                        num[0]++;
                    } else {
                        if (pre == 0) {
                            pre = cnt;
                            num[0]++;
                        } else {
                            pre = cnt;
                            tmp[0] += num[0] / 2;
                            num[0] = 1;
                        }
                    }
                }

                if (cnt == 0) {
                    if (num[1] != 0) {
                        tmp[1] += num[1]/2;
                        num[1] = 0;
                    }
                } else {
                    num[1]++;
                }
            }

            if (num[0] != 0) {
                tmp[0] += num[0]/2;
            }
            if (num[1] != 0) {
                tmp[1] += num[1]/2;
            }
            Max += sum - (m/4 - min(m/4, tmp[0]));
            Min += sum - min(m/4, tmp[1]);
        }
        cout << Min << " " << Max << endl;
    }
    return 0;
}