二分,求直线上覆盖所有点的最短时间

http://codeforces.com/group/aUVPeyEnI2/contest/230300/problem/E

参考自:https://blog.csdn.net/u013508213/article/details/49594691

题意:

给n个内存读取指针头,m个需要访问的内存地址(1?≤?n,?m?≤?1051?≤?n,?m?≤?105) ,每一秒钟,指针头可以向左移动或者向右移动一个单位,问最少需要多少时间,能把这些内存地址访问完。

solution:

二分固定时间t,ok函数的写法是:
当当前的指针头小于当前需要访问的内存节点时,指针头不断往前移动就好了;
当当前的指针头大于当前需要访问的内存节点时,需要做个比较:
首先是当前指针头先往左移动到需要访问的内存节点,再移动回来往前移动,此时还可以往前移动的时间是t?2?(head[i]?track[cnt])t?2?(head[i]?track[cnt]);
然后是当前指针头先往右移动足够远,然后再回来访问需要访问的内存节点,此时可以往前移动的时间是(t?(head[i]?track[cnt]))/2(t?(head[i]?track[cnt]))/2。
取二者大的往前移动即可。
若计数cnt>=m,说明时间充裕。

 1 /*************************************************************************
 2     > File Name:
 3     > Author: QWX
 4     > Mail:
 5     > Created Time: 2018/10/11 18:11:28
 6  ************************************************************************/
 7
 8
 9 //{{{ #include
10 #include<iostream>
11 #include<cstdio>
12 #include<algorithm>
13 #include<vector>
14 #include<cmath>
15 #include<queue>
16 #include<map>
17 #include<set>
18 #include<string>
19 #include<cstring>
20 #include<complex>
21 #include<bits/stdc++.h>
22 #define mp make_pair
23 #define pb push_back
24 #define first fi
25 #define second se
26 #define pw(x) (1ll << (x))
27 #define sz(x) ((int)(x).size())
28 #define all(x) (x).begin(),(x).end()
29 #define rep(i,l,r) for(int i=(l);i<(r);i++)
30 #define per(i,r,l) for(int i=(r);i>=(l);i--)
31 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)
32 #define cl(a,b) memset(a,b,sizeof(a))
33 #define fastio ios::sync_with_stdio(false);cin.tie(0);
34 #define lson l , mid , ls
35 #define rson mid + 1 , r , rs
36 #define INF 0x3f3f3f3f
37 #define LINF 0x3f3f3f3f3f3f3f3f
38 #define ll long long
39 #define ull unsigned long long
40 #define dd(x) cout << #x << " = " << (x) << ","
41 #define de(x) cout << #x << " = " << (x) << "\n"
42 #define endl "\n"
43 using namespace std;
44 //}}}
45
46 const int N=1e5+7;
47 ll a[N],b[N];
48 int n,m;
49 bool check(ll t)
50 {
51     int cnt=0;
52     rep(i,0,n){
53         if(t<abs(a[i]-b[cnt]))continue;
54         ll d=a[i];
55         if(a[i]<b[cnt])d+=t;
56         else d+=max((t-(a[i]-b[cnt]))/2,t-2*(a[i]-b[cnt]));
57         while(cnt<m&&b[cnt]<=d)cnt++;
58     }
59     return cnt>=m;
60 }
61
62 int main()
63 {
64     fastio;
65     cin>>n>>m;
66     rep(i,0,n)cin>>a[i];
67     rep(i,0,m)cin>>b[i];
68     ll l=0,r=1e11,ans=0;
69     while(l<=r){
70         ll mid=(l+r)>>1;
71         if(check(mid))r=mid-1,ans=mid;
72         else l=mid+1;
73     }
74     cout<<ans<<endl;
75     return 0;
76 }

原文地址:https://www.cnblogs.com/klaycf/p/9774613.html

时间: 10-11

二分,求直线上覆盖所有点的最短时间的相关文章

一条直线上N个线段所覆盖的总长度

原文:http://blog.csdn.net/bxyill/article/details/8962832 问题描述: 现有一直线,从原点到无穷大. 这条直线上有N个线段.线段可能相交. 问,N个线段总共覆盖了多长?(重复覆盖的地区只计算一次) ================================================ 解题思路: 可以将每个线段拆分成“单位1” 遍历所有线段,使用一个数组记录每个线段所走过的“单位1” 最后统计数组中被走过的中“单位1”的个数,即是所有线

已知直线上两点求直线的一般式方程

一般式方程在计算机领域的重要性 常用的直线方程有一般式 点斜式 截距式 斜截式 两点式等等.除了一般式方程,它们要么不能支持所有情况下的直线(比如跟坐标轴垂直或者平行),要么不能支持所有情况下的点(比如x坐标相等,或者y坐标相等).所以一般式方程在用计算机处理二维图形数据时特别有用. 已知直线上两点求直线的一般式方程 已知直线上的两点P1(X1,Y1) P2(X2,Y2), P1 P2两点不重合.则直线的一般式方程AX+BY+C=0中,A B C分别等于: A = Y2 - Y1 B = X1

poj3819 Coverage (求直线与圆的交占直线的百分比 )

题意:给你一条直线和若干个圆,求圆与直线相交的长度占整条直线的比例 解题思路:通过定比分点的方法求出圆与直线的交占圆的比例. 第一步:(确定投影的方向是x轴还是y轴) (1)当直线的line.s(x, y), line.e(x, y)的line.s.x与line.e.x不同一时候,这条直线能够等同于起点为line.s.x, line.e.x; (2)不满足(1)时(即line.s.x==line.e.x时),当直线的line.s(x, y), line.e(x, y)的line.s.y与line

二分求幂,快速求解a的b次幂

一个引子 如何求得a的b次幂呢,那还不简单,一个for循环就可以实现! void main(void) { int a, b; int ans = 1; cin >> a >> b; for (int i = 1; i <= b; i++) { ans *= a; } cout << ans; } 那么如何快速的求得a的b次幂呢?上面的代码还可以优化吗? 当然是ok的!下面就介绍一种方法-二分求幂. 二分求幂 所谓二分求幂,即是将b次幂用二进制表示,当二进制位k位

求直线与线段的交点

1,求点到直线的带符号距离: float getSignedDistance(点P,直线AB) //求点P到直线AB的带符号距离(当P在AB左侧时距离为正,右侧时为负) { dir=直线AB的方向向量 根据dir求出直线AB的左手法线向量leftNormal = (-dir.y,dir.x).normalized 线段AP在leftNormal上的投影即为P到直线AB的带符号距离: signedDistance=dot(AP,leftNormal); return signedDistance;

hdu 3641 数论 二分求符合条件的最小值数学杂题

http://acm.hdu.edu.cn/showproblem.php?pid=3641 学到: 1.二分求符合条件的最小值 /*==================================================== 二分查找符合条件的最小值 ======================================================*/ ll solve() { __int64 low = 0, high = INF, mid ; while(low <=

3403: [Usaco2009 Open]Cow Line 直线上的牛

3403: [Usaco2009 Open]Cow Line 直线上的牛 Time Limit: 3 Sec  Memory Limit: 128 MBSubmit: 71  Solved: 62[Submit][Status] Description 题目描述 约翰的N只奶牛(编为1到N号)正在直线上排队.直线上开始的时候一只牛也没有.接下来发生了S(1≤S≤100000)次事件,一次事件可能是以下四种情况之一: .一只奶牛加入队伍的左边(输入“AL”). .一只奶牛加入队伍的右边(输入“AR

HDU - 1588 Gauss Fibonacci (矩阵快速幂+二分求等比数列和)

Description Without expecting, Angel replied quickly.She says: "I'v heard that you'r a very clever boy. So if you wanna me be your GF, you should solve the problem called GF~. " How good an opportunity that Gardon can not give up! The "Prob

BZOJ 3403: [Usaco2009 Open]Cow Line 直线上的牛( deque )

直接用STL的的deque就好了... ---------------------------------------------------------------------- #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<deque> #define rep( i , n ) for( int i = 0 ; i <

二分求幂(快速求幂,二进制求幂)

二分求幂, 非递归求法(二进制求法): 比如 2^5就是5个2相乘,按照5的二进制求 3^10就是8个3相乘,再2个3相乘. 处理幂的二进制,具体实现代码如下: long long quickmulti(long long a,long long b) { long long res=1; while(b) { if(b&1) //如果最后一位为1,则res*=a; res*=a; a*=a; //a*=a b>>=1; //b%=2 } return res; }