题解：P16569 [ICPC 2026 APC] Time Display Stickers

· · 题解

P16569 [ICPC 2026 APC] Time Display Stickers

题意

给 n 张数字贴纸，拼 HH:MM（HH 为 00\sim 11，MM 为 00\sim 59），每个时间用 4 张，求最多拼几个。

思路

二分答案 mid。统计 cnt_{0\sim 9}，记 S_{05}=\sum_{i=0}^5 cnt_i。

拼 mid 个时间时，小时十位和分钟十位各有 mid 个位置必须用小数字（0 \sim 5）。小时十位优先用 0，不够的部分用 1，个数为 b=\max(0,mid-cnt_0)。小时十位用 1 会导致对应的小时个位也必须用小数字，所以强制用小数字的位置共 2mid+b 个。

由此得到两个充要条件：

  2. 小数字够用：2mid+b\le S_{05}。

满足这两条即合法。剩余位置无限制，总数字数 n\ge 4mid 由二分范围自动保证。时间复杂度 O(n+t\log n)。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int t, n;
string s;

void solve() {
  cin >> n >> s;
  vector<int> cnt(10);
  for (char c : s) {
    cnt[c - '0']++;
  }
  int S05 = 0;
  for (int i = 0; i <= 5; i++) {
    S05 += cnt[i];
  }
  int l = 0, r = n / 4;
  while (l < r) {
    int mid = l + r + 1 >> 1;
    if (mid > cnt[0] + cnt[1] / 2) {
      r = mid - 1;
      continue;
    }
    int b = max(0, mid - cnt[0]);
    if (2 * mid + b <= S05) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  cout << l << "\n";
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}