题解：CF803D Magazine Ad

题意

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

思路

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

代码

CPP

#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;
}

题解：CF803D Magazine Ad

文章操作

题意

思路

代码

相关推荐

评论

题解：CF803D Magazine Ad