CF729C Road to Cinema

2023-11-23 02:00
文章标签 road cinema cf729c

本文主要是介绍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\)时刻内到达,怎么判断呢?

解方程。youl.png

设 对于加油站分成的一小段路程\(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{且怒且悲且狂哉,是人是鬼是妖怪;不过是,心有魔债-《悟空》戴荃} \]

转载于:https://www.cnblogs.com/cbyyc/p/11594184.html

这篇关于CF729C Road to Cinema的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/414526

相关文章

【UVALive】5713 Qin Shi Huang's National Road System 最小生成树

传送门:【UVALive】5713 Qin Shi Huang's National Road System 题目大意:秦朝有n个城市,需要修建一些道路使得任意两个城市之间都可以连通。道士徐福声称他可以用法术修路,不花钱,也不用劳动力,但只能修一条路,因此需要慎重选择用法术修哪一条路。秦始皇不仅希望其他道路的总长度B尽量短(这样可以节省劳动力),还希望法术连接的两个城市的人口之和A尽量大,因此下

hdu 1598 find the most comfortable road (并查集 + 枚举)

题目:         链接:点击打开链接 思路:         对边排序,再枚举每条边,如果出现通路(findset(x) == findset(y))就结束。 代码: #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define

poj 3352 Road Construction(边连通+tarjan+缩点)

http://poj.org/problem?id=3352 题意:简化一下原题题意,意思就是给定一个连通图,问至少要加入几条边使得整个图变成一个边连通图,即图中任意两点都有两条以上的路径(不一定直接相连)。 思路:tarjan算法,设置一个low数组,在建立深搜树的过程中,我们会得到每个节点的low值,对于low值相等的节点在同一个双连通分量中。由于在同一个边连通分量中的点的“地

Road-SLAM:基于道路标线车道级精度SLAM

文章:Road-SLAM : Road Marking based SLAM with Lane-level Accuracy 作者:Jinyong Jeong, Younggun Cho, and Ayoung Kim1 编译:点云PCL 本文仅做学术分享,如有侵权,请联系删除。欢迎各位加入免费知识星球,获取PDF论文,欢迎转发朋友圈。内容如有错误欢迎评论留言,未经允许请勿转载! 对本文以及俯

道路 Road(百练,POJ)

题目链接: 1724 -- ROADS (poj.org) 题目描述: 思路: 这题目乍一看,是一个含有2个标尺的单源最短路问题,挺难处理的。 既然没法直接用最短路处理,那我们就“记录信息”,将花费的时间也记录进dp数组,然后跑“状态最短路”。 用f[i][j] 表示到达点i 且 总花费时间为j的最短距离,然后跑堆优化的dijkstra算法就好。由于不含有负边权,因此可以搞一个vis数

【语义分割】——又快又强:Deep Dual-resolution Networks for Real-time and Accurate Semantic Segmentation of Road

出处:哈尔滨工业大学 论文 code:暂未开源 关键词: 实时语义分割 语义分割是自动驾驶汽车了解周围场景的关键技术,对于实际的自动驾驶汽车来说,为了获得高精度的分割结果而花费大量的推理时间是不可取的。使用轻量级架构(编码器解码器或two-pathway)或推理在低分辨率图像。本文提出的模型在单张2080ti上DDRNet-slim能打到77.4% mIoU和230FPS,DDRNet

uva 1494 - Qin Shi Huang's National Road System(最小生成树)

题目链接:uva 1494 - Qin Shi Huang's National Road System 建成最小生成树之后,枚举两节点,然后删除路径上权值上最大的边。 #include <cstdio>#include <cstring>#include <cmath>#include <vector>#include <algorithm>using namespa

通往糊涂之路 The road to serfdom

最近被推送了一本书,哈耶克的............ 试一试,看看能不能看懂,也许是通往糊涂之路。

Internet Strategy: The Road to Web Services Solutions

版权声明:原创作品,允许转载,转载时请务必以超链接形式标明文章原始出版、作者信息和本声明。否则将追究法律责任。 http://blog.csdn.net/topmvp - topmvp Internet Strategy: The Road to Web Services Solutions reminds readers that several attempts have been m

HDU - 1596 find the safest road(Floyd算法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1596 Problem Description XX星球有很多城市,每个城市之间有一条或多条飞行通道,但是并不是所有的路都是很安全的,每一条路有一个安全系数s,s是在 0 和 1 间的实数(包括0,1),一条从u 到 v 的通道P 的安全度为Safe§ = s(e1)*s(e2)…*s(ek) e1,