P3017. Brownie Slicing G

发表于 2024-01-17 分类于洛谷阅读次数： Waline：本文字数： 532 阅读时长 ≈ 2 分钟

考点

二分
前缀和

题解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e2 + 50;
int R, C, A, B, pre[maxn][maxn];

int query(int x1, int y1, int x2, int y2) {
  return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
}

bool check(int s) {
  int valid = 0, x1 = 1, y1 = 1, x2 = 1, y2 = 1;
  while (x1 <= R && x2 <= R) {
    int block = 0;
    // 当前行数下，够不够竖切B个和为s的块
    while (y2 <= C) {
      if (query(x1, y1, x2, y2) >= s) {
        ++block;
        y1 = y2 + 1;
      }
      ++y2;
    }
    if (block >= B) {
      // 够的话，记录答案，并切换到下一横切
      ++valid;
      x2 = x1 = x2 + 1;
    } else {
      // 不够的话，新增行数
      ++x2;
    }
    y1 = y2 = 1;
  }
  return valid >= A;
}

int main() {
  cin >> R >> C >> A >> B;
  for (int i = 1; i <= R; ++i) {
    for (int j = 1; j <= C; ++j) {
      cin >> pre[i][j];
      pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
    }
  }
  int l = 0, r = pre[R][C];
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << r;
  return 0;
}

思路

由于横切和竖切组合有接近无数种切法，靠暴力枚举找答案是绝对行不通的。

题目要让最小值最大，考虑二分答案：

令s为所有蛋糕块里的最小值，

如果s是合法的，那么所有蛋糕块均为s的情况下，得到的块数一定是大于等于A * B的。

由此可以得到单调性：

s越大，总块数越小于A * B

s越小，总块数越大于A * B

若总块数大于等于A * B，说明s过小了，应该增大

若总块数小于A * B，说明s过大了，应该减小