I - Bus CodeForces - 864C(追车问题)

2024-04-16 03:18

本文主要是介绍I - Bus CodeForces - 864C(追车问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A bus moves along the coordinate line Ox from the point x = 0 to the point x = a. After starting from the point x = 0, it reaches the point x = a, immediately turns back and then moves to the point x = 0. After returning to the point x = 0 it immediately goes back to the point x = a and so on. Thus, the bus moves from x = 0 to x = a and back. Moving from the point x = 0 to x = a or from the point x = a to x = 0 is called a bus journey. In total, the bus must make k journeys.

The petrol tank of the bus can hold b liters of gasoline. To pass a single unit of distance the bus needs to spend exactly one liter of gasoline. The bus starts its first journey with a full petrol tank.

There is a gas station in point x = f. This point is between points x = 0 and x = a. There are no other gas stations on the bus route. While passing by a gas station in either direction the bus can stop and completely refuel its tank. Thus, after stopping to refuel the tank will contain b liters of gasoline.

What is the minimum number of times the bus needs to refuel at the point x = f to make k journeys? The first journey starts in the point x = 0.

Input
The first line contains four integers a, b, f, k (0 < f < a ≤ 106, 1 ≤ b ≤ 109, 1 ≤ k ≤ 104) — the endpoint of the first bus journey, the capacity of the fuel tank of the bus, the point where the gas station is located, and the required number of journeys.

Output
Print the minimum number of times the bus needs to refuel to make k journeys. If it is impossible for the bus to make k journeys, print -1.

Examples
Input
6 9 2 4
Output
4
Input
6 10 2 4
Output
2
Input
6 5 4 3
Output
-1
Note
In the first example the bus needs to refuel during each journey.

In the second example the bus can pass 10 units of distance without refueling. So the bus makes the whole first journey, passes 4 units of the distance of the second journey and arrives at the point with the gas station. Then it can refuel its tank, finish the second journey and pass 2 units of distance from the third journey. In this case, it will again arrive at the point with the gas station. Further, he can refill the tank up to 10 liters to finish the third journey and ride all the way of the fourth journey. At the end of the journey the tank will be empty.

In the third example the bus can not make all 3 journeys because if it refuels during the second journey, the tanks will contain only 5 liters of gasoline, but the bus needs to pass 8 units of distance until next refueling.

题意: 给出跑多少个轮回和加油站位置,最少加多少次油
思路: 追车问题有很多种,本题是直接贪心能不加油就不加油。
但本题还可以提前算出每一次加油的位置,然后在当前加油站位置时,看能否不需要加油,定义dp[i]:在第i次加油站位置出发时需要的最小加油次数,那么状态转移就是找到最大的那个不需要加油下一个加油站位置j,得到dp[i] = dp[j] + 1,表示从i出发的最小加油次数等于到了j加了次油再出发的最小加油次数。
(orz叉姐dp代码)。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int main()
{int a,b,f,k;scanf("%d%d%d%d",&a,&b,&f,&k);if(b <  f || b < (a - f) || (k > 1 && b < 2 * (a - f)) || (k > 2 && b < 2 * f)){puts("-1");return 0;}int ans = 0;int num = b;for(int i = 1;i <= k;i++){if(i == k && num >= a)break;if(i % 2){if(num < 2 * a - f){ans++;num = b - (a - f);}else{num -= a;}}else{if(num < a + f){ans++;num = b - f;}elsenum -= a;}}printf("%d\n",ans);return 0;
}
叉姐dp
#include <cstdio>
#include <vector>int main()
{int a, b, f_, k;scanf("%d%d%d%d", &a, &b, &f_, &k);long long f = f_;long long x = a;std::vector<long long> p { 0LL, f };for (int i = 1; i < k; ++ i) {f = 2 * x - f;p.push_back(f);x += a;}p.push_back(x);std::vector<int> dp(p.size());for (int i = p.size() - 2, j = (int)p.size() - 1; i >= 0; -- i) {while (p[j] - p[i] > b) {j --;}if (i == j) {puts("-1");return 0;}dp[i] = dp[j] + 1;}printf("%d\n", dp[0] - 1);
}

这篇关于I - Bus CodeForces - 864C(追车问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

mybatis和mybatis-plus设置值为null不起作用问题及解决

《mybatis和mybatis-plus设置值为null不起作用问题及解决》Mybatis-Plus的FieldStrategy主要用于控制新增、更新和查询时对空值的处理策略,通过配置不同的策略类型... 目录MyBATis-plusFieldStrategy作用FieldStrategy类型每种策略的作

linux下多个硬盘划分到同一挂载点问题

《linux下多个硬盘划分到同一挂载点问题》在Linux系统中,将多个硬盘划分到同一挂载点需要通过逻辑卷管理(LVM)来实现,首先,需要将物理存储设备(如硬盘分区)创建为物理卷,然后,将这些物理卷组成... 目录linux下多个硬盘划分到同一挂载点需要明确的几个概念硬盘插上默认的是非lvm总结Linux下多

Python Jupyter Notebook导包报错问题及解决

《PythonJupyterNotebook导包报错问题及解决》在conda环境中安装包后,JupyterNotebook导入时出现ImportError,可能是由于包版本不对应或版本太高,解决方... 目录问题解决方法重新安装Jupyter NoteBook 更改Kernel总结问题在conda上安装了

pip install jupyterlab失败的原因问题及探索

《pipinstalljupyterlab失败的原因问题及探索》在学习Yolo模型时,尝试安装JupyterLab但遇到错误,错误提示缺少Rust和Cargo编译环境,因为pywinpty包需要它... 目录背景问题解决方案总结背景最近在学习Yolo模型,然后其中要下载jupyter(有点LSVmu像一个

解决jupyterLab打开后出现Config option `template_path`not recognized by `ExporterCollapsibleHeadings`问题

《解决jupyterLab打开后出现Configoption`template_path`notrecognizedby`ExporterCollapsibleHeadings`问题》在Ju... 目录jupyterLab打开后出现“templandroidate_path”相关问题这是 tensorflo

如何解决Pycharm编辑内容时有光标的问题

《如何解决Pycharm编辑内容时有光标的问题》文章介绍了如何在PyCharm中配置VimEmulator插件,包括检查插件是否已安装、下载插件以及安装IdeaVim插件的步骤... 目录Pycharm编辑内容时有光标1.如果Vim Emulator前面有对勾2.www.chinasem.cn如果tools工

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

Java多线程父线程向子线程传值问题及解决

《Java多线程父线程向子线程传值问题及解决》文章总结了5种解决父子之间数据传递困扰的解决方案,包括ThreadLocal+TaskDecorator、UserUtils、CustomTaskDeco... 目录1 背景2 ThreadLocal+TaskDecorator3 RequestContextH

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2