感覺之前的*1900好簡單?

Problem - D - Codeforces

題意：

思路：

注意到寬度具有單調性，考慮二分寬度

然后限制了最大寬度，要使行數 <= k

那么在check里貪心，每行選的盡可能多

考慮雙指針，每次選長度為mid的區間，然后如果右端點 r 沒有指向換行符，那么 r 指向左邊離它最近的換行符

所以需要預處理一個位置左邊離它最近的換行符的位置

這樣就做完了

Code：

#include <bits/stdc++.h>using i64 = long long;const int N = 1e6 + 10;std::string s, s2;int k, len = 0, ns;
int pre[N];std::string substr(int l, int r) {return s.substr(l, r - l + 1);
}
bool check(int mid) {std::vector<std::string> res;int l = 1, r = 1;while(1) {if (l > ns || r > ns) break;while(r <= ns && r - l + 1 < mid) r ++;if (r == ns + 1) r --;if (s[r] != ' ' && s[r] != '-' && r != ns) r = pre[r];if (l > r) return false;res.push_back(substr(l, r));l = r + 1;r = l;}return res.size() <= k;
}
void solve() {std::cin >> k;getline(std::cin, s2);getline(std::cin, s);ns = s.size();s = " " + s;s = s + " ";for (int i = 1; i <= ns; i ++) {if (s[i] == '-' || s[i] == ' ') {pre[i] = i;}else {pre[i] = pre[i - 1];}}//std::cout << check(7) << "\n";int l = 1, r = ns;int ans = 0;while(l <= r) {int mid = l + r >> 1;if (check(mid)) {ans = mid;r = mid - 1;}else {l = mid + 1;}}std::cout << ans << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while (t--) {solve();}return 0;
}

?