1456 Supermarket

「1456 Supermarket」の編集履歴（バックアップ）一覧はこちら

「1456 Supermarket」(2006/04/17 (月) 01:42:14) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1456 Supermarket
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1456
**解答方針
「その日に売れるもので一番高いものを売る」という戦略を，10000日目から1日目まで，逆順に適用していく．
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(sc.hasNext()){
             int n = sc.nextInt();
             if(n==0) System.out.println("0");
             else{
                 Vector<Integer>[]prodset = (Vector<Integer>[])(new Vector<?>[10000]);
                 for(int i=0;i<10000;i++) prodset[i] = new Vector<Integer>();
                 
                 for(int i=0;i<n;i++){
                     int profit = sc.nextInt();
                     int dead = sc.nextInt()-1;
                     prodset[dead].add(profit);
                 }
                 Solver sol = new Solver(prodset);
                 System.out.println(sol.solve());
             }
         }
     }
 }
 
 class Solver{
     Vector<Integer>[] prodset;
     
     Solver(Vector<Integer>[] prodset){
         this.prodset = prodset;
     }
     
     public int solve(){
         int sum = 0;
         PriorityQueue<RevInteger> q = new PriorityQueue<RevInteger>();
         for(int i=9999;i>=0;i--){
             if(prodset[i].size()!=0){
                 for(int j=0;j<prodset[i].size();j++){
                     q.offer(new RevInteger(prodset[i].get(j)));
                 }
             }
             if(!q.isEmpty()){
                 sum += q.poll().i;
             }
         }
         return sum;
     }
 }
 
 class RevInteger implements Comparable<RevInteger>{
     int i;
     RevInteger(int x){
         i = x;
     }
     public int compareTo(RevInteger r){
         return -(i-r.i);
     }
 }