解题报告:luogu P3853 [TJOI2007]路标设置
2024-10-08 13:19:47
题目链接:P3853 [TJOI2007]路标设置
是个水二分,那你还\(WA\)。很简单,就是练了练和早上那题相似的题。
二分答案即可,复杂度\(O(Nlogl)\),可以通过本题。
不过,需要注意的是,若整除,\(cnt--\),否则和我一样成\(80pts\)。
\(Code\):
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int l,n,k,ans=0;
int a[1000005];
int judge(int x)
{
int cnt=0;
int last=0;
for(int i=0;i<=n+1;i++)
{
if(a[i]-last>x)
{
cnt+=(a[i]-last)/x;
if((a[i]-last)%x==0) cnt--;
}
last=a[i];
}
if(cnt>k) return 0;
else return 1;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("baoli.out","w",stdout);
scanf("%d%d%d",&l,&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int ll=1,rr=l;
a[n+1]=l;
while(ll<=rr)
{
int mid=(ll+rr)>>1;
if(judge(mid)) ans=mid,rr=mid-1;
else ll=mid+1;
}
printf("%d\n",ans);
return 0;
}
二分真神奇啊
最新文章
- IDEA 的 git 使用
- cssSlidy.js 响应式手机图片轮播
- ajax 异步插入图片到数据库(单图上传)
- rowcount和@@Rowcount的区别,获取insert、update、delete影响行数
- Android 利用日志消息调试程序
- webpack安装配置使用教程详解
- mysql事件
- UI:转自互联网资料
- jquery学习以及下载链接
- UVa11925 Generating Premutations
- 【android】adb连接几个常见问题(遇到再新增)
- 为outlook增加“邮件召回”功能
- CodeForces 747E Comments
- Jenkins的新建job和配置job
- Scala:集合类型Collection和迭代器
- POI往word模板中写入数据
- serialport控件的详细用法
- 关于iframe切换的问题
- mongodb数据库索引管理
- 为函数自定义bind方法实例页面
热门文章
- Python 基础之正则之二 匹配分组,正则相关函数及表达式修饰符
- Coursera 国内无法登陆问题
- Faster-RCNN Pytorch实现的minibatch包装
- Swift3.0-字符串和字符
- VS2019 发布单文件
- 十二 INPUT逻辑视图的配置,回显错误信息
- Java 调用系统系统可执行文件
- Pytorch本人疑问(2)model.train()和model.eval()的区别
- Linux centosVMware Nginx访问日志、Nginx日志切割、静态文件不记录日志和过期时间
- Python 之并发编程之进程上(基本概念、并行并发、cpu调度、阻塞 )