ABC445D Reconstruct Chocolate

d---reconstruct-chocolate">D - Reconstruct Chocolate

1. 题意梗概

给定 $N$ 个矩形巧克力碎片的尺寸 $(h_i, w_i)$，这些碎片是通过对一个 $H \times W$ 的大矩形进行 $N-1$ 次操作得到的；操作为切下一块放在桌上，手里留一块。求出每个碎片的左上角坐标 $(x_i, y_i)$。

Constraints

• $1 \leq H \leq 10^9$
• $1 \leq W \leq 10^9$
• $2 \leq N \leq 2\times 10^5$
• $1 \leq h_i \leq H$
• $1 \leq w_i \leq W$

2. 逻辑推导

这个 $N \leq 2e5$，就没法暴力了。

我们分析这个操作，每一次操作，都会让手上现有的巧克力切成两块，而且是沿着水平或者垂直线切的，这意味这什么？

这意味着切完之后这两块巧克力，要么 $h$ 相等，要么 $w$ 相等。

所以我们可以采用贪心模拟的策略，由于从最后一块开始拼装处理起来很麻烦，所以我们考虑从完整的巧克力开始切，考虑剩余的部分可以塞下谁。

维护当前剩余矩形的左上角坐标 (cx, cy) 和剩余尺寸 (ch, cw)。

1. 若存在碎片高度等于 ch，则该碎片填在当前列，cy 向右移动该碎片的宽度，cw 减少。

2. 若存在碎片宽度等于 cw，则该碎片填在当前行，cx 向下移动该碎片的高度，ch 减少。

然后就是快速查询的问题了，由于这题的 $H, W \le 1e9$，但是 $N \leq 2e5$，最直接的想法就是离散化，然后二分查询。

因为标准离散化写起来比较麻烦（苍天可鉴，代码复杂度高），我这里就偷懒采用 $map$ 作为离散化工具。

因为同一高度或者宽度的巧克力可能有很多，所以我开了一个 map< int, set< int > > 来存储，第一维是具体的值，第二位是符合条件的值的下标。

找到之后再通过 erase 函数删掉就行了，代码写起来很优雅，如下。

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 50;

struct Point { ll x, y; } ans[maxn];

map< int, set< int > > hh, ww;
ll h[maxn], w[maxn];
ll H, W;
int n;

void solve( )
{
    cin >> H >> W >> n;
    for( int i = 1; i <= n; ++ i )
    {
        cin >> h[i] >> w[i];
        hh[ h[i] ].insert( i );
        ww[ w[i] ].insert( i );
    }

    ll cx = 1, cy = 1;
    ll ch = H, cw = W;

    for( int i = 1; i <= n; ++ i )
    {
        int idx = -1;
        // 先判断高度有没有合适的
        if( hh.count( ch ) && !hh[ch].empty( ) )
        {
            idx = *hh[ch].begin( );
            ans[idx] = { cx, cy };
            cy += w[idx]; 
            cw -= w[idx];
        }
        // 如果没有高度合适的，就找长度合适的
        else if( ww.count( cw ) && !ww[cw].empty( ) )
        {
            idx = *ww[cw].begin( );
            ans[idx] = { cx, cy };
            cx += h[idx]; ch -= h[idx];
        }
        // 如果找到了能用的，就同步移除已经使用的碎片
        if( idx != - 1 )
        {
            hh[h[idx]].erase( idx );
            ww[w[idx]].erase( idx );
        }
    }
    // 输出
}