1. 首頁 > 生活百科 > >

Codeforces 1672 E. notepad.exe

生活百科

題意這是一道交互題 ， 有n個字符串，每個字符串長度:0-2000, n :0-2000有一個機器對他進行排版，你可以給他一個每行的最大寬度w，那么每行只能放長度為w的字符；每行相鄰兩個字符串之間至少有一個空格，每行結尾可以不用，機器會按照貪心原則進行排版，保證排版后的高度盡量小 。你可以進行n+30次詢問 ， 每次詢問你可以給個w ， 他會給你排版后高度h，讓你求出w*h的最小值 。
做題吐槽這題很典型的構造題，不會就是不會，會了一下子就會做了，這種題感覺就是要一下子找到題目的突破點，挖掘出這類題目的特征，感覺自己還是菜，每個突破點想到了 ， 但是沒串連起來，繼續加油！
提示1. 答案的范圍變化是很小的，變化范圍只有0-20002. 當 h= 1 的時候，很顯然是最優的w是每個字符空一格 3. 當求出h = 1時候的答案h*w = s時，在h改變時，最多就是換行符號替換了空格，s變化為s-(h-1),并且需要整除h ， 那么只有一個點 s/h 滿足4. 這樣就做出來了，先二分找出h=1時，w的最小值 ， 對后續每個h高度詢問一次檢查一下就可得到最終解
反正很玄妙，如何想到變化范圍小，如何想到整除，我感覺只能這種題只能從極值考慮，例如h=1，h=n這些點看看有沒有什么特征 ， 根據特征再去推理過程
代碼#include<bits/stdc++.h>using namespace std;void run() {int n;cin >> n;int l = 2 * n - 1, r = n * 2000 + n, flag = -1;while (l <= r) {int mid = (l + r) >> 1;int x;cout << "? " << mid << endl;cin >> x;if (x == 1) {flag = mid;r = mid - 1;} else {l = mid + 1;}}int s = flag;//cout<<s<<endl;int ans = s;for (int i = 2; i <= n; i++) {cout << "? " << s / i << endl;int x;cin >> x;if (x)ans = min(ans, x * (s / i));}cout << "! " << ans << endl;}int main() {run();return 0;}【Codeforces 1672 E. notepad.exe】

    推薦閱讀