首页 > 代码库 > PAT 1033

PAT 1033

2024-07-30 23:33:00   222人阅读

JAVA没法玩耍系列，这道题限时10ms，所以我也不知道到底对不对，反正示例是正确的

贪心法，对于我来说很绕的贪心法。

 

分为下面的步骤

在满油情况下能够跑到的所有加油站中搜索

1. 如果该加油站比当前加油站要便宜，则加油到刚好跑到这个加油站，继续下一轮

2. 如果到了终点，则加油到终点，用哨兵保证这一点

3. 如果在这段区间，没有找到比当前加油站更便宜的加油站，则加油到满油

 

其实就是顺序没处理好所以做了很长时间，原来的做法是依次向后找到最便宜的加油站，如果超过最大距离了又怎么样，这就不如限定在一个范围内找加油站了

感觉学到了一些，要把通用情况放到最外面判断。

 

代码如下：

  1 import java.util.*;  2 import java.io.*;  3   4 class FastReader{  5     BufferedReader reader;  6     StringTokenizer tokenizer;  7       8     public FastReader(InputStream stream){  9         reader = new BufferedReader(new InputStreamReader(stream), 1 << 22); 10         tokenizer = null; 11     } 12      13     public String next(){ 14         while (tokenizer == null || !tokenizer.hasMoreTokens()){ 15             try {  16                 tokenizer = new StringTokenizer(reader.readLine()); 17             } catch (Exception e){ 18                 //System.out.println(-1); 19                 throw new RuntimeException(e); 20             } 21         } 22          23         return tokenizer.nextToken(); 24     } 25      26     public int next_int(){ 27         return Integer.parseInt(next()); 28     } 29      30     public float next_float(){ 31         return Float.parseFloat(next()); 32     } 33 } 34  35 class StationInfo{ 36     float dist; 37     float price; 38 } 39  40 public class Main { 41     public static void main(String[] args){ 42         FastReader reader = new FastReader(System.in); 43         float cap, dist, avg_dist; 44         int num; 45          46         cap = reader.next_float(); 47         dist = reader.next_float(); 48         avg_dist = reader.next_float(); 49         num = reader.next_int(); 50          51         float longest_run = avg_dist * cap; 52         StationInfo[] stations = new StationInfo[num + 1]; 53         for (int i = 0; i < num; i++){ 54             stations[i] = new StationInfo(); 55             stations[i].price = reader.next_float(); 56             stations[i].dist = reader.next_int(); 57         } 58         stations[num] = new StationInfo(); 59         stations[num].dist = dist; 60         stations[num].price = 0; 61          62         Arrays.sort(stations, new Comparator<StationInfo>(){ 63             public int compare(StationInfo s1, StationInfo s2){ 64                 return (s1.dist - s2.dist < 0.0f) ? -1 : 1; 65             } 66         }); 67          68         for (int i = 0; i < stations.length - 1; i++){ 69             if (stations[i + 1].dist - stations[i].dist > longest_run){ 70                 float max_travel = stations[i].dist + longest_run; 71                 System.out.println(String.format("The maximum travel distance = %.2f", max_travel)); 72                 return; 73             } 74         } 75          76         if (stations[0].dist != 0.0f) 77             System.out.println(String.format("The maximum travel distance = %.2f", 0.0f)); 78          79         int cur_station = 0; 80         float cur_oil = 0.0f; 81         float cost_sum = 0.0f; 82         while (cur_station < num){ 83             float cur_run = 0.0f; 84             int next_station = cur_station; 85             int lowest_price_station = cur_station; 86             float lowest_price = Float.MAX_VALUE; 87             boolean solved = false; 88             while (true){ 89                 float cur_dist = stations[next_station + 1].dist - stations[next_station].dist; 90                 if (cur_dist + cur_run > longest_run) 91                     break; 92                 cur_run += cur_dist; 93                 next_station++; 94                  95                 if (stations[next_station].price < stations[cur_station].price){ 96                     float need_oil = cur_run / avg_dist; 97                     float add_oil = (cur_oil > need_oil) ? 0.0f : (need_oil - cur_oil); 98                     cost_sum += add_oil * stations[cur_station].price; 99                     100                     cur_oil = cur_oil + add_oil - need_oil;101                     cur_station = next_station;102                     103                     solved = true;104                     break;105                 }106                 107                 /*108                 if (next_station != cur_station){109                     if (stations[next_station].price < lowest_price){110                         lowest_price_station = next_station;111                         lowest_price = stations[next_station].price;112                     }113                 }114                 */115             }116             117             if (!solved){118                 float add_oil = cap - cur_oil;119                 cost_sum += add_oil * stations[cur_station].price;120                 cur_oil += add_oil;121                 cur_oil -= cur_run / avg_dist;122                 cur_station = next_station;123             }124         }125         126         System.out.println(String.format("%.2f", cost_sum));127     }128 }

 

PAT 1033


联系
我们