hdu 1257

http://acm.hdu.edu.cn/showproblem.php?pid=1257

題意：有個攔截系統，這個系統在最開始可以攔截任意高度的導彈，但是之后只能攔截不超過這個導彈高度的導彈，現在有N個導彈需要攔截，問你最少需要多少個攔截系統

思路：按高度由大到小進行排序，然后在遍歷這個，用一個數組繼續每個導彈攔截系統可以攔截的最低高度，如果發現當前的點需要在所以的攔截系統攔截的最低高度之前，那么在加一個攔截系統

?

import java.awt.Point;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintStream;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws FileNotFoundException{
    //    InputReader cin = new InputReader(System.in);
        Scanner cin = new Scanner(System.in);
        int t;
        Point p[] = new Point[20005];
        for(int i =0;i<20005;i++)
            p[i] = new Point();
        int cnt[] = new int[20005];
        while(cin.hasNext()){
            t = cin.nextInt();
            for(int i =0;i<t;i++){
                p[i].x = cin.nextInt();
                p[i].y = i;
            }
            Arrays.sort(p,0,t,new zxc());
            cnt[0] = p[0].y;
            int res = 1;
            for(int i = 1,j;i<t;i++){
            //    System.out.println(p[i].x+"   "+p[i].y);
                for(j = 0;j<res;j++){
                    if(p[i].y>cnt[j]){
                        cnt[j] = p[i].y;
                        break;
                    }
                }
                if(j==res){
                    cnt[res++] = p[i].y;
                }
            }
            System.out.println(res);
        }
    }
}


class zxc implements Comparator<Point>{

    
    public int compare(Point a, Point b) {
        if(a.x==b.x)
            return a.y-b.y;
        return b.x-a.x;
    }
    
}

?