題意
這是一道互動題，有n個字串，每個字串長度:0-2000, n :0-2000
有一個機器對他進行排版，你可以給他一個每行的最大寬度w，那么每行只能放長度為w的字符；
每行相鄰兩個字串之間至少有一個空格，每行結尾可以不用，機器會按照貪心原則進行排版，保證排版后的高度盡量小，
你可以進行n+30次詢問，每次詢問你可以給個w，他會給你排版后高度h，讓你求出w*h的最小值，
做題吐槽
這題很典型的構造題，不會就是不會，會了一下子就會做了，這種題感覺就是要一下子找到題目的突破點，挖掘出這類題目的特征，感覺自己還是菜，每個突破點想到了，但是沒串連起來，繼續加油！
提示
1. 答案的范圍變化是很小的，變化范圍只有0-2000
2. 當 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/520661.html
標籤：其他
上一篇：Shell腳本1