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】

Codeforces 1672 E. notepad.exe

推荐阅读

形容教室里很多人的成语

芋头和香芋一样吗？芋头什么人不能多吃

白羊座最适合的运动

电脑版微信怎么发朋友圈电脑版微信怎么发朋友圈视频

《四季豆一定要焯水吗》

鱼鳞痣怎么祛除掉鱼鳞痣怎么祛除

保护视力的绘画作品保护视力的绘画作品画法

伊美婷成分伊美婷胶原蛋白安全吗

江苏省公务员abc类区别江苏省公务员abc类的区别

关于来不及诉说简述来不及诉说

肉煎饺的做法步骤肉煎饺的做法步骤

属兔的适合住什么楼层最好住几楼大吉？

职工医保和城乡居民医保哪个划算？交哪个好

越在乎你才会越嫌弃你的星座，天蝎上榜！

王丽云主演的电视剧有哪些王丽云演的全部电视剧

荞麦茶的功效有哪些荞麦茶有什么作用功效

攀升MaxBook P2参数_攀升MaxBook P2配置

大连金普新区文旅场馆7月19日起取消查验核酸报告

发朋友圈运动的幽默句子发朋友圈运动句子

铝锅煮汤对人体有害吗，不建议经常使用铝锅煮汤