天津市做网站的公司,定制网站开发哪个好,进黑龙江建设网站用哪个浏览器好,广州网站建设网络推广传送门.
解析
只需二分枚举空旷指数即可 对于单次判断的check函数#xff0c;可以相当于n个路标把路面分成n1个间隔#xff0c;而对于每个间隔[l,r]和空旷指数x#xff08;边界已有路标#xff09;#xff0c;所需路标应为#xff1a;
(r-l-1)/x#xff08;比如[2,5…传送门.
解析
只需二分枚举空旷指数即可 对于单次判断的check函数可以相当于n个路标把路面分成n1个间隔而对于每个间隔[l,r]和空旷指数x边界已有路标所需路标应为
(r-l-1)/x比如[2,5],x3,显然不用所以需减1 这样每段复杂度为O1 check复杂度则为ON 可以得到解决
update on 2022.3.17
感谢 沉迷小说 提出的关于二分上界的问题只需要赋值为 lll 即可已经修正
代码
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includeiostream
#includestring
#includequeue
#includevector
using namespace std;
const int M1e9;
int l,n,k;
int a[100500]{ },d[100500];
bool check(int x){int num0;for(int i1;in1;i){num(d[i]-1)/x;}return numk;
}
int main(){scanf(%d%d%d,l,n,k);a[0]1;for(int i1;in;i){scanf(%d,a[i]);d[i]a[i]-a[i-1];//记录每段间隔长度}d[n1]l-a[n];int st0,edl;while(sted){int mid(sted) 1;if(check(mid)) edmid;else stmid1;}printf(%d,st);return 0;
}AC快乐
