Road to Cinema"/>
CF729C Road to Cinema
写在前面
又开始\(CF\)之旅了,嘻嘻:-)
Idea
链接
这是一道二分,教练推荐的。
仔细看题后,求的是:找到一个能够在要求时间内到达的最小油量
讲车辆按照价格从小到大排序,第一个油箱大于最小油量的车子就是\(Ans\)
如何求? 贪心。
在这之前解一个方程组:设在\(s\;m\)之内,加速的位移是\(x\;m\),平速的位移为\(y\;m\),则
\[ \begin{cases}x+y=s\\x+y \times 2=t\end{cases} \]
解得\(x=2 \times s-t\)。
来分析下样例一
\(x=2 \times s-t=6\),即加速位移为6,把路程分为两段:\(3\;And\;5\)
第一段全加速,耗油6;第二段3加速,2平速,耗油8。
即\(Ans=\max(6,8)=8\),容易得出答案10;
但是,会有一种情况卡掉它
\(e.g:\)我们把道路分成两段,\(5\;And\;5\),\(x=2\),最小耗油量为7
但可以看出来,还有更好的答案;
接下来我们这样考虑:对于每个油量\(v\),我们可以判断出能不能在\(t\)时刻内到达,怎么判断呢?
解方程。
设 对于加油站分成的一小段路程\(l\),我们设加速里程是\(x\),平速里程是\(y\),可以得出
\[ \begin{cases}x+y=l\\x \times 2+y \le v\end{cases} \]
解得\(x \le v-s\),但若想时间最小,加速位移也就最大(应该没问题吧),即\(x=v-l\)
则\(x+2 \times y=3 \times l-v\)
注意:
\(v < l\)时,无论如何油量都不够走完这段路程,\(v > 2 \times l\)时,这一段路程可以一直加速,也就是时间是L。也就是说我们上面算出来的这一段的最短时间\(3 \times l-v\)是当\(l \le v \le 2 \times L\)时的取值。
Code
struct Node{int p,f;inline bool operator<(const Node&x)const{return p<x.p;}
}c[maxn];
int d[maxn],f[maxn];
int n,k,s,t;
inline bool check(int x){int res=0;for(int i=0;i<=k;i++){int l=d[i];if(x>l*2) res+=l;else if(x<l) return 0;else res+=l*3-x;}return res<=t;
}
inline int solve(){int l=1,r=inf;while(l<=r){int mid=l+r>>1;if(check(mid)) r=mid-1;else l=mid+1;}return l;
}
signed main(){n=read(); k=read(); s=read(); t=read();for(int i=0;i<n;i++) c[i].p=read(),c[i].f=read();sort(c,c+n);for(int i=0;i<k;i++)f[i]=read();sort(f,f+k);for(int i=1;i<k;i++)d[i]=f[i]-f[i-1];d[0]=f[0];d[k]=s-f[k-1];int minn=solve();int ans=0;for(int i=0;i<n;i++)if(c[i].f>=minn){ans=c[i].p;break;}if(minn==inf) puts("-1");else if(!ans) puts("-1");else printf("%d",ans);return 0;
}
\[ The \quad End \]
\[ \text{且怒且悲且狂哉,是人是鬼是妖怪;不过是,心有魔债-《悟空》戴荃} \]
转载于:.html
更多推荐
CF729C Road to Cinema
发布评论