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

推荐阅读

炒薏米怎么吃最除湿薏米怎么吃除湿效果好呢

另一个伊甸拉克雷娅技能介绍,技能提升

阿房宫赋翻译全文阿房宫赋翻译

关于环球法律评论简述环球法律评论

怎么用CE去查找游戏的技能基址（怎么恢复用ce修改的游戏)

元旦能回河北吗 2022元旦可以回河北吗

儿童买什么保险好

社保交15年和17年的区别相差多少钱？最低要交多少年？

未知错误3004怎么回事？未知错误3004的解决方法[推荐]

光遇禁阁光之翼有几个

法律系实习周记

王者荣耀钻石有什么用-钻石作用详解

1972年属鼠的人婚配查询表

枣花馒头花样做法枣花馒头花样制作方法

双子座的智商有多高

桃花劫是什么意思以及最后的结果

蜻蜓的比喻句怎么写有关蜻蜓的比喻句

黑潮之上艾尔莎好用吗,艾尔莎卡牌技能全面评测,欢迎阅读

散养鸡技术散养鸡蛋和养殖鸡蛋的区别

世上最大的蜈蚣在哪里有多大