CF803D Magazine Ad，数据读取有坑

小码匠

发布于 2024-01-14 20:32:41

730

发布于 2024-01-14 20:32:41

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好！我是小码匠。

原本晚上还以为有AtCoder，后来老码农查了下，是改到明晚。

跟老码农谈判，晚上刷一道题，然后让我再复习会。

这道题读数据卡了会，一开始死活数据读不进来，是因为我忘记注释掉这块代码。

//    // 提升cin、cout效率
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.tie(nullptr);

后来注释掉，就能顺利读入数据。第一次提交就挂了，做CF题就没顺利过呢？

数据范围又开小了，直接看翻译的内容，给开成

const int MAX_NUM = 1e5 + 5;

实际应该开成

const int MAX_NUM = 1e6 + 5;

下面分享AC的代码：

#include <bits/stdc++.h>

using namespace std;
const int MAX_NUM = 1e6 + 5;
int s[MAX_NUM], n = 0, m;
bool check(int k) {
    int cnt = 0;
    int ans = 0;
    for (int i = 0; i <= n; ++i) {
        if (s[i] > k) {
            return false;
        }
        if (cnt + s[i] <= k) {
            cnt += s[i];
        } else {
            ++ans;
            cnt = s[i];
        }
    }

    ans += cnt != 0;
    return ans <= m;
}

void best_coder() {
    cin >> m;
    getchar(); // 读入换行符
    int l = 0, r;
    string c;
    getline(cin, c);
    int len = 0;
    r = c.size();
    for (int i = 0; i < r; ++i) {
        if (c[i] == '-' || c[i] == ' ') {
            s[n++] = len + 1;
            l = max(l, s[n - 1]);
            len = 0;
        } else {
            ++len;
        }
    }

    s[n] = len;

    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << r;
}

void happy_coder() {

}

int main() {
//    // 提升cin、cout效率
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-01-14，如有侵权请联系 cloudcommunity@tencent.com 删除

int