CF1819B The Butcher

这篇博客主要是讲述作者在 CodeForces 的一道题目 CF1819B The Butcher 的解题过程。在解题思路方面，文章提到了需要讨论两种情况切割出一个长最大的矩形或者切割出一个宽最大的矩形，并递归判断剩余小矩形是否满足构成大矩形的条件。在实现方面，作者给出了具体的代码实现，并使用了 STL 中的 vector 和 sort 等常用函数。最后，文章总结了这道题目的时间复杂度和解题思路的优势。

题目大意

对于一个矩形，可以对它进行横向切割或竖向切割得到两个小矩形，并将其中一个放在盒子里（矩形不会翻转，且之后不再对盒子里的矩形进行切割）。这样，在 $n-1$ 次切割后将会得到 $n$ 个矩形。现给出这 $n$ 个矩形的长和宽，要求找到所有可能的最初大矩形。

思路

首先，初始矩形的面积是可以累加求出的。不难发现第一次分割要么切割出一个长最大的矩形，要么切割出一个宽最大的矩形，可以分两种情况讨论。 判断出第一个切割出的矩形后，可以求出剩下的大矩形的长和宽，问题转化为剩下的所有小矩形能否构成指定长和宽的大矩形。如果这些小矩形可以构成大矩形，则一定满足小矩形中最长（或宽）的长与大矩形的长（或宽）相等，递归判断剩下的小矩形能否构成除去小矩形后的大矩形即可。 由于在过程中大矩形的长和宽单调不增，因此可以分别对小矩形按长和宽两次降序排列，在处理过程中只需遍历一次即可。时间复杂度受排序的限制，为 $O(nlogn)$ 。

代码

code

struct Rect {
    long long h, w;
    bool exi;
} r[200010];
Rect *hh[200010], *ww[200010];
int n, hp, wp;
long long a;
int cmp_h(Rect *x, Rect *y) { return x->h > y->h; }
int cmp_w(Rect *x, Rect *y) { return x->w > y->w; }
bool operator==(Rect x, Rect y) { return x.w == y.w && x.h == y.h; }
int judge(long long H, long long W) {
    if (H == 0 || W == 0)
        return 1;
    if (H < 0 || W < 0)
        return 0;
    while (hh[hp]->exi == 0 && hp < n)
        hp++;
    while (ww[wp]->exi == 0 && wp < n)
        wp++;
    if (hp >= n || wp >= n)
        return 0;
    if (hh[hp]->h == H) {
        hh[hp]->exi = 0;
        return judge(H, W - hh[hp]->w);
    }
    if (ww[wp]->w == W) {
        ww[wp]->exi = 0;
        return judge(H - ww[wp]->h, W);
    }
    return 0;
}
void solve() {
    vector<Rect> ans;
    a = wp = hp = 0;
    cin >> n;
    rep(i, 0, n - 1) {
        cin >> r[i].h >> r[i].w;
        r[i].exi = 1;
        ww[i] = hh[i] = r + i;
        a += r[i].h * r[i].w;
    }
    sort(hh, hh + n, cmp_h);
    sort(ww, ww + n, cmp_w);
    if ((a - hh[0]->h * hh[0]->w) % hh[0]->h == 0) {
        hh[0]->exi = 0;
        if (judge(hh[0]->h, (a - hh[0]->h * hh[0]->w) / hh[0]->h)) {
            ans.pb(
                {hh[0]->h, (a - hh[0]->h * hh[0]->w) / hh[0]->h + hh[0]->w, 1});
        }
    }
    wp = hp = 0;
    rep(i, 0, n - 1) { r[i].exi = 1; }
    if ((a - ww[0]->w * ww[0]->h) % ww[0]->w == 0) {
        ww[0]->exi = 0;
        if (judge((a - ww[0]->w * ww[0]->h) / ww[0]->w, ww[0]->w)) {
            ans.pb(
                {(a - ww[0]->w * ww[0]->h) / ww[0]->w + ww[0]->h, ww[0]->w, 1});
        }
    }
    if (ans.size() == 2 && ans[0] == ans[1])
        ans.resize(1);
    cout << ans.size() << endl;
    rep(i, 0, ans.size() - 1) { cout << ans[i].h << " " << ans[i].w << endl; }
}