题解：P16480 [GKS 2014 #A] Cut Tiles
xuduang
·
·
题解
为啥题解区都这么复杂。
大瓷砖可以分裂为小的瓷砖。建议画图来理解过程。
::::info[分裂过程]
::::
可以想到从大到小做。枚举 $j$ 代表现在处理到了第 $j$ 位，记录现在有多少个能放 $2^j$ 的位置 $rst$，如果 $rst>cnt_j$，那说明可以直接放下，否则还需要多买一些大瓷砖。
那么现在就要快速计算买一块大瓷砖可以做出多少个大小为 $2^j$ 的空位。由上文分裂过程可知，原来没用完的空位可以分裂为现在的空位。但是也可能可以截一些之前没用完的边角料下来用，这个要如何计算呢？
一个不难发现的事实是，每当 $m$ 这一位是 $1$ 的时候，就会出现之前大的方块没填满的一条边角料现在可以用了。而这个边角料可以放下 $2 \times \frac{m}{2^j}-1$ 个 $j \times j$ 的方块。这一块建议画图理解或是看别的题解里面的图辅助理解。
于是这样就可以快速算出 $m \times m$ 的瓷砖可以放下 $k$ 个 $j \times j$ 的瓷砖，不够的话多买 $\lfloor \frac{cnt_j-rst}{k} \rfloor$ 个大瓷砖即可。
时间复杂度 $O(n + \log m)$。
可以让所有的数值对 $n$ 取 $\min$，这样不会影响答案并且不用担心爆 long long。
其实看代码还是很明白的。
```cpp
#include <bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define fi first
#define se second
#define pb emplace_back
#define mk make_pair
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 10, inf = 1e18, M = 2e6 + 10, mod = 1e9 + 7;
const double eps = 1e-8;
int n, m, a[N], cnt[35];
void solve(int csd) {
cin >> n >> m; int K = __lg(m);
memset(cnt, 0, sizeof cnt);
for(int i = 1; i <= n; i++) cin >> a[i], cnt[a[i]]++;
int rst = 0, all = 0, k = 1;
for(int j = K; ~j; j--) {
if(j != K && (m >> j) & 1) {
int del = (m >> j) * 2 - 1;
rst = min(rst + all * del, n), k = min(k + del, n);
}
if(rst < cnt[j]) {
int res = (cnt[j] - rst + k - 1) / k;
rst += res * k, all += res;
}
rst -= cnt[j];
k *= 4, rst *= 4;
k = min(k, n), rst = min(rst, n);
}
cout << "Case #" << csd << ": " << all << "\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
for(int t = 1; t <= T; t++) solve(t);
return 0;
}
```