/**
Codeforces Round #200 (Div. 1) C. Read Time 二分
链接:https://codeforces.com/contest/343/problem/C
题意：n个刷子 m个原点 n个刷子同时左右进行刷 问最少的时间使得m个点都能够被刷到;
分析 :
直接二分暴力查找答案 由于刷子存在的点和原点都是递增的因此每次看枚举的次数看是否能够遍历所有的点即可;
简单的来说就是确定一个左端点r一直往右拉比较当前刷子所能移动的次数 和 枚举次数 即可;
******tricks*********
开始没发现n个刷子是可以同时进行刷的;
对于0的情况一定要特殊考虑;
因为满足0的其余一定是满足条件的;
*/#include
#define ll long long
using namespace std;
const int maxn=1e5+7;
ll h[maxn],p[maxn];
int n,m;
bool judge(ll x){
int l=1,r=1;
for(int i=1;
i<=n;
i++){
ll tmp=abs(p[r]-p[l])+min(abs(p[r]-h[i]),abs(p[l]-h[i]));
while(r<=m&&tmp<=x){
r++;
tmp=abs(p[r]-p[l])+min(abs(p[r]-h[i]),abs(p[l]-h[i]));
}
l=r;
if(r==m+1) return true;
}
return false;
}int main (){
scanf("%d %d",&n,&m);
for(int i=1;
i<=n;
i++) scanf("%lld",&h[i]);
for(int i=1;
i<=m;
i++) scanf("%lld",&p[i]);
if(judge(0)) {
cout<<0<1){
mid=(l+r)/2;
if(judge(mid)) r=mid;
else l=mid;
}
printf("%lld\n",r);
return 0;
} 【CodeForces|Codeforces Round #200 (Div. 1) C. Read Time 二分】
推荐阅读
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- Codeforces|Codeforces Round #643 (Div. 2) B.Young Explorers