Codeforces #380 738C. Road to Cinema
传送门：http://codeforces.com/contest/738/problem/C
题目翻译
一个人要在不超过 t 的时间从 0 到达 S。
这个人只可以在0点选择租一种车子价格为Pi、油箱为Vi，路上有一些加油点可以瞬间把车子加满油。
车子有两种行驶方式，消耗1点油，2分钟走1千米 或者 消耗2点油，1分钟走2千米。
求租车最小费用。
题解
二分最小可行油箱大小
然后线性查找可行油箱的最小费用
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int Maxn=2e5; int n,k,s,t; struct Crent{ int c,v; }; Crent cr[Maxn+5]; int g[Maxn+5]; inline bool judge(int cV){ int now=0,mTime=0; for (int i=1;i<=k;i++){ if (now>=g[i]) continue; int dist=g[i]-now; int nowTime=dist*2; int left=cV-dist; if (left<0) return false; nowTime-=min(dist,left); mTime+=nowTime; now=g[i]; } return mTime<=t; } inline bool cmp(int a,int b){ return a<b; } int main(){ scanf("%d%d%d%d",&n,&k,&s,&t); for (int i=1;i<=n;i++) scanf("%d%d",&cr[i].c,&cr[i].v); for (int i=1;i<=k;i++) scanf("%d",&g[i]); g[++k]=s; sort(g+1,g+k+1,cmp); int left=0,right=1e9,AnsV=1e9+1; while(left<=right){ int mid=(left+right)/2; if (judge(mid)){ AnsV=min(AnsV,mid); right=mid-1; }else{ left=mid+1; } } int Ans=-1; for (int i=1;i<=n;i++){ if (cr[i].v>=AnsV) if (Ans==-1 || Ans>cr[i].c) Ans=cr[i].c; } printf("%d\n",Ans); return 0; } |
原文链接：Codeforces #380 738C. Road to Cinema
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!