pat1033汽车加油问题（Java贪心）

这题就是说汽车开始0油，然后给出总路程，每公里汽车能够跑的路程，测试用例数量，
每个测试用例给出价钱和距离。这题刚开始没有思路，以前见过没有思路后来绕过去没想到在pat上又遇到了，看了题解后来恍然大悟，这个贪心技巧以前没有见过。

• 具体的贪心思路：核心：将油预储存，将油分成块，背包里可能多个地方的油但是不一定用，每到一个地方都要把油加满。这里就是处理的核心关键：加油的时候淘汰背包里面价格比当前位置贵的油。每次使用油的时候，有限用最便宜的油，如果没用完还要考虑。
• 用treemap存入<距离，价格>,因为要从0开始经过。保证可能达到的所有情况可以到达。用优先队列存入当前油，当然，你还要记录油的总量，钱的总量和当前位置，还要判断油是否能够到达当前点。
• 但是这个是double类型变量，，准确度。。。吐槽一下，我在牛客的最后一个案例错了，但是到pat官网上全部通过，我复制牛客上AC代码到pat上就过了三组数据，，真坑！附上代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Comparator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) throws IOException {
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		double cmax=in.nval;//最大容量
		in.nextToken();double distance=in.nval;//距离
		in.nextToken();double ave=in.nval;//每一个气能跑的距离
		in.nextToken();int n=(int)in.nval;//数量
		Map map=new TreeMap();
		map.put(distance, Double.MAX_VALUE);
		for(int i=0;iq1=new PriorityQueue(cmp);//两个做中转处理
		Queueq2=new PriorityQueue(cmp);
		for(double k:map.keySet())
		{ //if(k>=distance) {k=distance;} if(oilnumber*ave<(k-index)) {b=true;index =oilnumber*ave;break;}//跑到截至 else { double length=0; while(length(k-index))//能够多出部分 { oilnumber-=(k-index-length)/ave; exam.value-=(k-index-length)/ave; money =(k-index-length)/ave*exam.price; length=k-index; q1.add(exam); } else//跑不完 { money =exam.value*exam.price; oilnumber-=exam.value; length =exam.value*ave; } } index=k; //开始加油工作//淘汰旧油 if(k=distance) {break;} } //out.println(" " k " " map.get(k) " " money);
		}
		if(index==distance)
		out.println(String.format("%.2f", money));
		else out.println("The maximum travel distance = " String.format("%.2f", index));
		out.flush();

	}
public	static Comparatorcmp=new Comparator() {
	@Override
	public int compare(oil o1, oil o2) { return (o1.price-o2.price)>0?1:-1;
	} };
public	static class oil
	{
	public	double price;//价格
	public	double value;//余量
		public oil() {
		}
		public oil(double price,double value)
		{ this.price=price; this.value=value;
		}
	}
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
 

大体的逻辑没啥问题，对集合的掌握理解要高，可能有些小瑕疵如果发现请找出来。

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/82498058