题解：P14782 [NERC 2025] Alphabet City
_xhz_
·
·
题解
思路如下：
每个街道 i 的字母计数 $
\text{cnt}[i][c]
所有街道合计（每个街道有 $m$ 份）：
\text{total}[c] = \sum_{i=1}^{n} \text{cnt}[i][c]\cdot m
所有街道的字母需求总和：
\text{sum1}[c] = \sum_{i=1}^{n} \text{cnt}[i][c]
---
对某个街道 $l$ ，移除其 $m$ 份字母后剩余库存
\text{have}_l(c) = \text{total}[c] - \text{cnt}[l][c]\cdot m
---
如果街道 $l$ 至少要做 $1$ 份路牌，则需求
\text{need}_{l,1}(c)=\text{cnt}[l][c]
判断是否满足：
\text{have}_l(c) \ge \text{cnt}[l][c]
---
其余 $(n-1)$ 个街道每个做 $k$ 份路牌：
k\cdot(\text{sum1}[c]-\text{cnt}[l][c])
加上街道 $l$ 的一份：
\text{need}_l(c)=k(\text{sum1}[c]-\text{cnt}[l][c])+\text{cnt}[l][c]
可行条件就是：
\text{have}_l(c)\ge \text{need}_l(c)
---
对 $k$ 做二分搜索，找到满足全部字母 $c$ 的最大 $k$ 。
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> w(n);
vector<array<ll,26>> freq(n);
array<ll,26> tot{};
array<ll,26> sum{};
for (int i = 0; i < n; i++) {
cin >> w[i];
for (char ch : w[i]) freq[i][ch - 'A']++;
for (int c = 0; c < 26; c++) {
tot[c] += freq[i][c] * 1LL * m;
sum[c] += freq[i][c];
}
}
for (int i = 0; i < n; i++) {
bool flag1 = true;
for (int c = 0; c < 26; c++) {
ll h = tot[c] - freq[i][c] * 1LL * m;
if (h < freq[i][c]) flag1 = false;
}
if (!flag1) {
cout << -1 << (i + 1 == n ? "" : " ");
continue;
}
ll L = 0, R = 2e12, best = 0;
while (L <= R) {
ll mid = (L + R) / 2;
bool flag2 = true;
for (int c = 0; c < 26; c++) {
ll h = tot[c] - freq[i][c] * 1LL * m;
ll need = mid * (sum[c] - freq[i][c]) + freq[i][c];
if (h < need) { flag2 = false; break; }
}
if (flag2) best = mid, L = mid + 1;
else R = mid - 1;
}
cout << best << (i + 1 == n ? "" : " ");
}
}
```