文档章节

题目1437:To Fill or Not to Fill

微洛Willow
 微洛Willow
发布于 2017/03/18 15:24
字数 872
阅读 9
收藏 0

题目1437:To Fill or Not to Fill

时间限制:1 秒

内存限制:128 兆

特殊判题:

提交:3412

解决:779

题目描述:

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.

输入:

For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,...N. All the numbers in a line are separated by a space.

输出:

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.

样例输入:

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
50 1300 12 2
7.10 0
7.00 600

样例输出:

749.17
The maximum travel distance = 1200.00

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            double Cmax = scan.nextInt();
            double D = scan.nextInt();
            double Davg = scan.nextDouble();
            int N = scan.nextInt();
            if (Cmax > 100 || D > 30000 || Davg > 20 || N > 500) {
                continue;
            }
            List<Station> stationList = new ArrayList<Station>();
            for (int i = 0; i < N; i++) {
                stationList.add(new Station(scan.nextDouble(), scan.nextDouble()));
            }
            Collections.sort(stationList);
            double maximum = 0.00, price = 0.00, oil = 0.00, availableDis = Cmax * Davg;
            int cheapIndex = 0;
            Station cheapStation;
            // 循环结束flag为true
            boolean flag = false;
            if (N == 0 || stationList.get(0).dis != 0) {
                System.out.println("The maximum travel distance = 0.00");
                continue;
            }
            for (int i = 0; i < N && !flag;) {
                cheapStation = null;
                cheapIndex = -1;
                // 查找经过的最便宜加油站,若经过的加油站价格低于出发的加油站(即i)价格,直接结束循环
                for (int j = i + 1; j < N; j++) {
                    // 判断加油站距离不大于满油能走的距离
                    if ((stationList.get(j).dis - stationList.get(i).dis <= availableDis)
                            && stationList.get(j).dis < D) {
                        // 若参与比较的加油站,油价低于当前加油站,则结束循环
                        if (stationList.get(j).price < stationList.get(i).price) {
                            cheapStation = stationList.get(j);
                            cheapIndex = j;
                            break;
                        }
                        // 若参与比较的加油站为第一个,则记录为最便宜的加油站(cheapStation)
                        if (j == i + 1) {
                            cheapStation = stationList.get(j);
                            cheapIndex = j;
                        }
                        // 若参与比较的加油站为比较范围中最低价格,则覆盖原来的cheapStation
                        if (stationList.get(j).price < cheapStation.price) {
                            cheapStation = stationList.get(j);
                            cheapIndex = j;
                        }
                    } else {
                        break;
                    }
                }
                //1.可直接走到终点,当前位置最低价格或最后一个加油站 
                if (stationList.get(i).dis + availableDis >= D) {
                    // 若当前加油站为最后一个,或为最便宜的加油站,则直接在此处加油至终点
                    if (cheapStation == null || stationList.get(i).price <= cheapStation.price) {
                        oil = oil - (D - stationList.get(i).dis) / Davg;
                        if (oil < 0) {
                            price += (0 - oil) * stationList.get(i).price;
                        }
                        System.out.printf("%.2f\n", price);
                        flag = true;
                        break;
                    }
                }
                //2.不能到达终点,没有可以经过的加油站,计算加满油能走的最大距离
                if (cheapStation == null) {
                    maximum = stationList.get(i).dis + availableDis;
                    System.out.printf("The maximum travel distance = %.2f\n",maximum);
                    flag = true;
                    break;
                }
                //3.不能到达终点,当前加油站为最便宜价格,加满油 ,开到后面经过的最便宜加油站
                if(stationList.get(i).price<cheapStation.price){
                    price += (Cmax-oil)*stationList.get(i).price;
                    oil = Cmax;
                    //oil = Cmax - (cheapStation.dis-stationList.get(i).dis)/Davg;
                } 
                //4.不能到达终点,适量加油,开到能经过的最便宜的加油站
                oil = oil - (cheapStation.dis-stationList.get(i).dis)/Davg;
                if(oil<0){
                    price+=(0-oil)*stationList.get(i).price;
                    oil = 0;
                }
                i = cheapIndex;
            }
        }
    }
}
 
class Station implements Comparable<Station> {
    double price;
    double dis;
 
    Station() {
    }
 
    Station(double price, double dis) {
        this.price = price;
        this.dis = dis;
    }
 
    @Override
    public String toString() {
        return "Station [price=" + price + ", dis=" + dis + "]";
    }
 
    @Override
    public int compareTo(Station o) {
        return (int) (dis - o.dis);
    }
}

© 著作权归作者所有

微洛Willow
粉丝 0
博文 12
码字总数 7854
作品 0
浦东
程序员
私信 提问
JFinal 插件MailerPlugin报错

@JFinal 你好,想跟你请教个问题:我用JFinal插件,本地调试能够发送,放到线上邮箱能够登录,但是发送邮件的时候报错 IOException while sending, closing java.net.SocketException: Conne...

freedomcat
2016/01/19
611
0
Subclipse 1.8.15 发布,Eclipse 的 SVN 插件

Subclipse 1.8.15 发布,改进记录包括: JavaHL 升级到 Subversion 1.7.6 消除递归检索从库中的属性,从工作副本创建分支的svn:externals属性固定的修订。 (1436) 修复了清理动作的标签 (1...

oschina
2012/08/16
1K
3
spark 运行 清洗数据 失败

ResultStage 5 (collectAsList at ManyMac.java:42) failed in 88.705 s 17/03/25 03:27:14 INFO scheduler.DAGScheduler: Job 2 failed: collectAsList at ManyMac.java:42, took 364.05806......

天池番薯
2017/03/25
201
0
学习express之实现Json的Post请求

参考:http://yijiebuyi.com/blog/38f1437bf5b43fcf90e6529a81f258f1.html 参考:http://yijiebuyi.com/blog/90c1381bfe0efb94cf9df932147552be.html 1)引入模块body-parser var bodyParse......

cs_sharp
2015/09/08
596
0
Iptables+Nginx+Tomcat6

Ubuntu 9.10 X86 没有安装apache,就是个干净系统 想装nginx+mysql+Tomcat6 只安装nginx,使用缺省配置文件 我主要是想实现NIGINX实现tomcat6的负载. TOMCAT6也是默认端口没有改变过 . 出现的...

蝶衣人生
2010/03/03
2.1K
5

没有更多内容

加载失败,请刷新页面

加载更多

好程序员web前端分享逻辑运算

  一门计算机语言,编程的核心在于逻辑思想,当我们在编写程序的时候,逻辑是否通顺,是能否正确写出程序的关键,可以说如果你掌握了逻辑,那么你就踏入了计算机编程的大门。 &&与 || 或 ...

好程序员IT
21分钟前
1
0
我的Linux系统开始学习的过程

我的Linux系统开始学习的过程 Linux系统,不知大家是否了解。接触计算机不多或对计算机不感冒的人可能对其比较陌生,曾经的我也是。上大学前的我的确对Linux一无所知,那时候接触面窄,都没有...

linuxCool
22分钟前
1
0
让自己的网站可以被搜索

第一步:先注册一个属于自己的域名,这个域名是独一无二的。推荐到主机屋注册一个,其实在哪里注册都是一样的,但是主机屋提供免费的地址解析服务(只对在主机屋注册的域名免费)。 主机屋官...

WinkJie
24分钟前
2
0
全站加速(DCDN)- IP应用加速产品解读

5月22日下午15点,阿里云全站加速(DCDN)-IP应用加速如期发布。IP应用加速是阿里云自主研发的一款更高效、更安全、更便捷的动态加速产品,结合阿里云CDN本身的资源优势,利用就近接入、智能...

阿里云官方博客
27分钟前
1
0
k8s常用命令

1.创建deployment资源kubectl apply -f nginx.yml2.删除deployment资源kubectl delete -f nginx.yml3.查看deployment资源基本信息deployment资源(运行的服务资源)kubectl get...

平头哥-Enjoystudy
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部