Error message here!

Hide Error message here!

Error message here!

Hide Error message here!

Error message here!

Close

# 贪心算法

AdamLeeXi 2019-02-16 17:49:00 阅读数:222 评论数:0 点赞数:0 收藏数:0

[1 , 5] ，[2 , 3]，[4 , 5]，[7 , 8]，[4 , 8]，[2 , 7]，[2 , 6] 为一间教室中的课表时间，[上课时间，下课时间]，问该教室最多可以安排几节课

1033 To Fill or Not to Fill （25 分）

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

### Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers:

### Output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print The maximum travel distance = X where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

### Sample Input 1:

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300


### Sample Output 1:

749.17


### Sample Input 2:

50 1300 12 2
7.10 0
7.00 600


### Sample Output 2:

The maximum travel distance = 1200.00这道题目要求我们判断能否从杭州到达目的地，以及寻找从杭州到目的地最少的加油费用这道题目使用贪心算法，每次寻找加满油之后可以到达的加油站中：1.若是有比当前加油站便宜的加油站，则将汽油加到刚好可以到达第一个比该加油站便宜的站点，为什么不选择最便宜的那一个，而是选择第一个比当前加油站便宜的站点呢？我们可以考虑一种特殊情况：若是当前的加油站的汽油特别特别贵，而下一个紧挨着他的加油站便宜得多，而他可以可以到达的最便宜的站点要加满油才过得去，显然这种情况下寻找最便宜的站点是不合适的。2.若是所有可以到达的汽油站的价格都高于当前的加油站，这时我们要判断：是否可以直接开到终点呢？如果可以，则加油到可以开到终点的油量就欧克。如果不可以，那么寻找可以到达的加油站中最便宜的加油站，加满油开过去。具体代码实现如下：
import java.util.*;
public class Main {
public static void main(String args[])
{
Scanner scanner = new Scanner(System.in) ;
float tank = scanner.nextFloat() ;
float dis = scanner.nextFloat() ;
float rundis = scanner.nextFloat() ;
float num = scanner.nextFloat() ;
scanner.nextLine() ;
Map<Float,Float> map = new HashMap<>() ;
List<Float> list = new ArrayList<>() ;
for(int i = 0 ; i < num ; i ++)
{
float money = scanner.nextFloat() ;
float distance = scanner.nextFloat() ;
map.put(distance, money) ;
}
scanner.close();
Collections.sort(list);
float gas = 0 ;
float sumdis = 0 ;
float summoney = 0 ;
for(int i = 0 ; i < num - 1 ; i ++)
{
float d1 = list.get(i) ;
float d2 = list.get(i+1) ;
if(d2 - d1 > tank*rundis)
{
System.out.print("The maximum travel distance = ");
System.out.printf("%.2f",sumdis+rundis*tank);
return ;
}
float min = 100 ;
for(int j = i+1 ; j < num ; j ++)
{
if(map.get(list.get(j)) <= min && list.get(j) - d1 <= tank*rundis)
{
i = j - 1;
d2 = list.get(j) ;
min = map.get(d2) ;
if(min < map.get(d1)) break ;
}
}
float needgas = (d2 - d1)/rundis ;
if(map.get(d2) <= map.get(d1))
{
if(gas > needgas)
gas -= needgas ;
else
{
summoney += (needgas-gas)*map.get(d1) ;
gas = 0 ;
}
}
else
{
if(dis - d1 <= tank*rundis)
{
needgas = (dis - d1)/rundis ;
if(gas >= needgas)
{
System.out.printf("%.2f",summoney);
return ;
}
else
{
summoney += (needgas - gas)*map.get(d1) ;
System.out.printf("%.2f",summoney);
return ;
}
}
summoney += (tank-gas)*map.get(d1) ;
gas = tank - needgas ;
}
sumdis = d2 ;
}
if(dis - sumdis > tank*rundis)
{
System.out.print("The maximum travel distance = ");
float diss = sumdis+rundis*tank ;
System.out.printf("%.2f",diss);
return ;
}
else
{
float needgas = (dis - sumdis)/rundis ;
if(gas >= needgas) System.out.printf("%.2f",summoney);
else
{
summoney += (needgas-gas)*map.get(sumdis) ;
System.out.printf("%.2f",summoney);
}
}
}
}

 

https://www.cnblogs.com/handsomelixinan/p/10388553.html

30万现金开奖等你来领