美词网站建设,淘宝客做自己网站,qq登录网页版,查询网站服务器提供商http://acm.hdu.edu.cn/showproblem.php?pid1257 题意#xff1a;有个拦截系统#xff0c;这个系统在最开始可以拦截任意高度的导弹#xff0c;但是之后只能拦截不超过这个导弹高度的导弹#xff0c;现在有N个导弹需要拦截#xff0c;问你最少需要多少个拦截系统 思路1257 题意有个拦截系统这个系统在最开始可以拦截任意高度的导弹但是之后只能拦截不超过这个导弹高度的导弹现在有N个导弹需要拦截问你最少需要多少个拦截系统 思路按高度由大到小进行排序然后在遍历这个用一个数组继续每个导弹拦截系统可以拦截的最低高度如果发现当前的点需要在所以的拦截系统拦截的最低高度之前那么在加一个拦截系统 1 import java.awt.Point;2 import java.io.BufferedReader;3 import java.io.File;4 import java.io.FileNotFoundException;5 import java.io.FileOutputStream;6 import java.io.IOException;7 import java.io.InputStream;8 import java.io.InputStreamReader;9 import java.io.OutputStream;
10 import java.io.PrintStream;
11 import java.lang.reflect.Array;
12 import java.math.BigInteger;
13 import java.util.Arrays;
14 import java.util.Comparator;
15 import java.util.Random;
16 import java.util.Scanner;
17 import java.util.StringTokenizer;
18
19 public class Main {
20 public static void main(String[] args) throws FileNotFoundException{
21 // InputReader cin new InputReader(System.in);
22 Scanner cin new Scanner(System.in);
23 int t;
24 Point p[] new Point[20005];
25 for(int i 0;i20005;i)
26 p[i] new Point();
27 int cnt[] new int[20005];
28 while(cin.hasNext()){
29 t cin.nextInt();
30 for(int i 0;it;i){
31 p[i].x cin.nextInt();
32 p[i].y i;
33 }
34 Arrays.sort(p,0,t,new zxc());
35 cnt[0] p[0].y;
36 int res 1;
37 for(int i 1,j;it;i){
38 // System.out.println(p[i].x p[i].y);
39 for(j 0;jres;j){
40 if(p[i].ycnt[j]){
41 cnt[j] p[i].y;
42 break;
43 }
44 }
45 if(jres){
46 cnt[res] p[i].y;
47 }
48 }
49 System.out.println(res);
50 }
51 }
52 }
53
54
55 class zxc implements ComparatorPoint{
56
57
58 public int compare(Point a, Point b) {
59 if(a.xb.x)
60 return a.y-b.y;
61 return b.x-a.x;
62 }
63
64 } 转载于:https://www.cnblogs.com/Tree-dream/p/7451790.html