首页 > 代码库 > CodeForces 738C Road to Cinema
CodeForces 738C Road to Cinema
二分答案。
油量越多，显然通过的时间越少。可以二分找到最小的油量，可以在$t$时间内到达电影院。
一个油箱容量为v的车通过长度为L的路程需要的最小时间为$max(L,3*L-v)$。计算过程如下：
假设普通速度运行了距离$a$，加速运行了距离$b$，则$a+b=L$，即$b=L-a$。
因为$a+2*b≤v$，所以$a≥2*L-v$。所花时间为$2*a+b≥3*L-v$，因为最小需要$L$的时间，所以取个$max$。按照$max(L,3*L-v)$一段一段加起来验证就可以了。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0);void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}struct X{ long long c,v;}p[200010];int n,k;long long s,t,g[200010];int f[200010];bool cmp(X a, X b){ return a.v<b.v;}bool check(long long x){ long long tt=0; for(int i=0;i<k;i++) { long long len=g[i+1]-g[i]; tt=tt+max(len,3*len-x); } if(tt<=t) return 1; return 0;}int main(){ cin>>n>>k>>s>>t; for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].c,&p[i].v); for(int i=1;i<=k;i++)scanf("%lld",&g[i]); g[0]=0; g[k+1]=s; k++; sort(g,g+1+k); sort(p+1,p+1+n,cmp); long long mxlen=g[1]-g[0]; for(int i=0;i<=k-1;i++) { long long len=g[i+1]-g[i]; mxlen=max(mxlen,len); } long long INF=0x7FFFFFFF; INF=INF*INF; long long L=mxlen,R=1000000000,limit=-1; while(L<=R) { long long mid=(L+R)/2; if(check(mid)) limit=mid,R=mid-1; else L=mid+1; } if(limit==-1) printf("-1\n"); else { long long mn=INF; for(int i=1;i<=n;i++) { if(p[i].v<limit) continue; mn=min(mn,p[i].c); } if(mn==INF) printf("-1\n"); else printf("%lld\n",mn); } return 0;}
CodeForces 738C Road to Cinema
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。