题解：CF803D Magazine Ad

zhangmuning1016 · 2025-05-16 16:07:40 · 题解

题意

这道题是在满足行数限制的条件下，找到广告所需的最小宽度。确定每行可容纳的最大字符数，通过 二分查找 来优化这个过程。

思路

• 将给定的广告划分为不超过 k 行，找到最小的可能宽度，使得所有行的长度都不超过这个宽度。
• 用二分来确定最小宽度。对于每个宽度，检查是否可行。
• 对于每个宽度，模拟划分过程，统计行数。如果行数不超过 k，则可行。

  代码

  
  #include<bits/stdc++.h>
  using namespace std;
  const int MAXN = 1e6 + 5;
  int a[MAXN];
  bool fun(int ll, int width, int k) {
  int lines = 1;
  int len = 0;
  for (int i = 0; i < ll - 1; ++i) {
      int S = a[i + 1] - a[i];
      if (S > width) {
          return false;  //长度超过宽度，不可行
      }
      if (len + S <= width) {
          len += S;
      } else {
          ++lines;
          len = S;
      }
      if (lines > k) {
          return false;  //行数超过限制，不可行
      }
  }
  return true;  //所有条件满足，可行
  }

int main() { int k; cin >> k; cin.ignore(); string ad; getline(cin, ad);

int LL = 0;

a[LL++] = -1;  // 起始位置

for (int i = 0; i < ad.length(); ++i) {
    if (ad[i] == ' ' || ad[i] == '-') {
        a[LL++] = i;
    }
}
a[LL++] = ad.length() - 1;  // 结束位置

int l = 1;
int r = ad.length();
int ans = ad.length();

while (l <= r) {
    int mid = (l + r) / 2;

    if (fun(LL, mid, k)) {
        ans = mid;
        r = mid - 1;
    } else {
        l = mid + 1;
    }
}

cout << ans << endl;
return 0;

}