真题算法考点

钢板填坑问题
路面有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