本文共 3182 字，大约阅读时间需要 10 分钟。
钢板填坑问题
路面有n个坑，需要用m个钢板盖住 m个钢板钱不一样，尺寸不一样 固定给出m个钢板，看怎么组合能用总费用最少的钢板盖住所有坑 例 2 3 50 80 50 5 90 3 80 4 结果1 7 给定2个坑，3个钢板 每个坑的直径 每个钢板的直径和费用且成对出现 最后计算是第一个案例，最少使用的费用是7 思路是按费用排序，每次最少费用的钢板该直径最大的坑，保证这一个钢板肯定只能盖住这一个坑。这样后面的钢板 也能对应盖一个坑 3 2 3 50 80 50 5 90 3 80 4 3 5 50 80 40 50 5 79 3 70 4 75 7 40 5 5 10 50 40 50 60 50 50 54 60 11 45 22 49 51 35 16 80 53 70 1 80 99 90 84 55 23 给定框架 package sasst.web; import java.util.Scanner; public class Solution { static int N,M; static int Hi[] = new int[1000]; static int Si[] = new int[10000]; static int Pi[] = new int[10000]; public static void main(String[] args) { Scanner sc= new Scanner(System.in); int T = sc.nextInt(); for(int test_case =1;test_case<=T;++test_case){ N=sc.nextInt(); M=sc.nextInt(); for(int i = 0;i Hi[i]=sc.nextInt(); } for(int i =0; i Si[i]=sc.nextInt(); Pi[i]=sc.nextInt(); } System.out.println(); System.out.println("keng size "); for(int i = 0;i System.out.print(Hi[i]+" "); } System.out.println(); System.out.println("gangban "); for(int i =0; i System.out.print(Si[i]+" "+Pi[i]+" "); } System.out.println(); } } } 具体实现 注意 前面数组构造时的长度，改成N,M，而不是1000具体值，以防后面比较时数组中出现大量0影响排序结果 new时候的语句要在输入以后，而不是最上面声明 import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Solut { static int N,M; static int Hi[]; static int Si[]; static int Pi[]; static MtDate[] mtDate; public static void main(String[] args) { Scanner sc= new Scanner(System.in); int T = sc.nextInt(); for(int test_case =1;test_case<=T;++test_case){ N=sc.nextInt(); M=sc.nextInt(); Hi = new int[N]; for(int i = 0;i Hi[i]=sc.nextInt(); } Si=new int[M]; Pi=new int[M]; mtDate = new MtDate[M]; for(int i =0; i Si[i]=sc.nextInt(); Pi[i]=sc.nextInt(); mtDate[i]=new MtDate(); mtDate[i].Si = Si[i]; mtDate[i].Pi = Pi[i]; } Comparator mt = new MyT(); Arrays.sort(mtDate,mt); Arrays.sort(Hi); int price = 0; for(int i=N-1;i>=0;i--){ int t = getPrice(Hi[i]); if(t>0)price=price+t; else {price=-1; break;} } System.out.println(); System.out.print(test_case+","+price); } } static int getPrice(int hhi) { for(int i=0;i if(mtDate[i].Si>=hhi&&!mtDate[i].used){ mtDate[i].used=true; return mtDate[i].Pi; } } return -1; } } class MtDate{ public int Si,Pi; public boolean used= false; } class MyT implements Comparator{ public int compare(MtDate o1,MtDate o2){ if(o1.Pi return -1; }else if(o1.Pi>o2.Pi){ return 1; }else{ return 0; } } } 20170713 真算法 查找避难所个数 1 2 3 7 8 9 2 9 8 6 5 2 2 3 2 5 6 7 1 2 3 2 6 8 2 3 1 5 7 9 如上面数组，每行值表示海拔高度，发大水时寻找紧急避难所，需要根据海拔高度判断 避难所的最大个数。 给定测试用例 5 5 7 数组的长和宽 7是洪水高度 然后找避难所时，避难所得海拔高度要高于即>洪水高度。符合要求的避难所必须是在其 上下左右至少一个方向里也有一个符合要求的避难所。同时重要的是还要找到避难所的最大 个数。比如这里洪水高度是7，那么8和9符合要求，但矩阵中有多个8和9，这是相当于有 三处避难所，而每个避难所的个数都是2，因此找出的避难所个数最大是2.可想如果矩阵 中有一处是8和9,10，另一处是8和9，那么最大避难所的个数是3而不是2. 自己的实现思路是双循环，每一个元素查找时判断前后左右四个方向是不是有挨着的。 如果判断这个值符合条件，就继续判断这个值得坐标和迁移符合要求的元素的值坐标 是不是挨着如果挨着计数器继续增加，不挨着计数器将为0，这样找出最大的count。 注意 寻找前一个坐标是要初始化prei=-1，prej=-1 因此第一个符合条件的值的坐标count++,prei=i,prej=j 以后符合条件值的坐标要判断该点坐标和前一个点坐标是否挨着再count++,且prei=i,prej=j 20170727 32位字符数，如10000000000000000000000000000000 和 00000000000000000000000000000001 左边的数中1可以向左或向右移动，问向哪边移动次数最少可以移动成为右边的数字 移动结果L 1 向左移动一次是右面数字 0000000000000000000000000010101 0000000000000000000000000000001 左面没法移动成右面所以结果是 -1转载地址：http://awwal.baihongyu.com/