PKU Judge Online 2431 Expedition

■2431 Expedition

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

view plainprint?

1. package p2431;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. // AC  
12. public class Main{  
13.   
14.     Scanner sc=new Scanner(System.in);  
15.   
16.     int INF=1<<28;  
17.     double EPS=1e-9;  
18.   
19.     void run(){  
20.         int n=sc.nextInt();  
21.         Stop[] stops=new Stop[n+1];  
22.         for(int i=n-1; i>=0; i--){  
23.             stops[i]=new Stop();  
24.             stops[i].pos=sc.nextInt();  
25.             stops[i].fuel=sc.nextInt();  
26.         }  
27.         stops[n]=new Stop();  
28.         int l=sc.nextInt();  
29.         int p=sc.nextInt();  
30.         for(int i=0; i<=n; i++)  
31.             stops[i].pos=l-stops[i].pos;  
32.         Arrays.sort(stops, new Comparator<Stop>(){  
33.             public int compare(Stop p1, Stop p2){  
34.                 return p1.pos-p2.pos;  
35.             }  
36.         });  
37.         int pos=0;  
38.         int ans=0;  
39.         PriorityQueue<Integer> q=new PriorityQueue<Integer>();  
40.         for(int i=0; i<=n; i++){  
41.             int d=stops[i].pos-pos;  
42.             while(p-d<0){  
43.                 if(q.isEmpty()){  
44.                     println("-1");  
45.                     return;  
46.                 }  
47.                 p-=q.poll();  
48.                 ans++;  
49.             }  
50.             p-=d;  
51.             pos=stops[i].pos;  
52.             q.offer(-stops[i].fuel);  
53.         }  
54.         println(""+ans);  
55.     }  
56.   
57.     class Stop{  
58.         int pos;  
59.         int fuel;  
60.     }  
61.   
62.     void print(String s){  
63.         System.out.print(s);  
64.     }  
65.   
66.     void println(String s){  
67.         System.out.println(s);  
68.     }  
69.   
70.     public static void main(String[] args){  
71.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
72.         new Main().run();  
73.     }  
74. }  

package p2431;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1<<28;
    double EPS=1e-9;

    void run(){
        int n=sc.nextInt();
        Stop[] stops=new Stop[n+1];
        for(int i=n-1; i>=0; i--){
            stops[i]=new Stop();
            stops[i].pos=sc.nextInt();
            stops[i].fuel=sc.nextInt();
        }
        stops[n]=new Stop();
        int l=sc.nextInt();
        int p=sc.nextInt();
        for(int i=0; i<=n; i++)
            stops[i].pos=l-stops[i].pos;
        Arrays.sort(stops, new Comparator<Stop>(){
            public int compare(Stop p1, Stop p2){
                return p1.pos-p2.pos;
            }
        });
        int pos=0;
        int ans=0;
        PriorityQueue<Integer> q=new PriorityQueue<Integer>();
        for(int i=0; i<=n; i++){
            int d=stops[i].pos-pos;
            while(p-d<0){
                if(q.isEmpty()){
                    println("-1");
                    return;
                }
                p-=q.poll();
                ans++;
            }
            p-=d;
            pos=stops[i].pos;
            q.offer(-stops[i].fuel);
        }
        println(""+ans);
    }

    class Stop{
        int pos;
        int fuel;
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}