真題算法考點(diǎn)

鋼板填坑問(wèn)題
路面有n個(gè)坑，需要用m個(gè)鋼板蓋住
m個(gè)鋼板錢不一樣，尺寸不一樣
 固定給出m個(gè)鋼板，看怎么組合能用總費(fèi)用最少的鋼板蓋住所有坑
例 
 2 3
  50 80
  50 5 90 3 80 4


結(jié)果1 7
給定2個(gè)坑，3個(gè)鋼板
 每個(gè)坑的直徑
 每個(gè)鋼板的直徑和費(fèi)用且成對(duì)出現(xiàn)
 最后計(jì)算是第一個(gè)案例，最少使用的費(fèi)用是7
思路是按費(fèi)用排序，每次最少費(fèi)用的鋼板該直徑最大的坑，保證這一個(gè)鋼板肯定只能蓋住這一個(gè)坑。這樣后面的鋼板
 也能對(duì)應(yīng)蓋一個(gè)坑
 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();
    }
   }
  }


具體實(shí)現(xiàn)
 注意
 前面數(shù)組構(gòu)造時(shí)的長(zhǎng)度，改成N,M，而不是1000具體值，以防后面比較時(shí)數(shù)組中出現(xiàn)大量0影響排序結(jié)果
new時(shí)候的語(yǔ)句要在輸入以后，而不是最上面聲明
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 真算法
查找避難所個(gè)數(shù)
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
如上面數(shù)組，每行值表示海拔高度，發(fā)大水時(shí)尋找緊急避難所，需要根據(jù)海拔高度判斷
避難所的最大個(gè)數(shù)。
給定測(cè)試用例
5 5 7 數(shù)組的長(zhǎng)和寬 7是洪水高度
然后找避難所時(shí)，避難所得海拔高度要高于即>洪水高度。符合要求的避難所必須是在其
上下左右至少一個(gè)方向里也有一個(gè)符合要求的避難所。同時(shí)重要的是還要找到避難所的最大
個(gè)數(shù)。比如這里洪水高度是7，那么8和9符合要求，但矩陣中有多個(gè)8和9，這是相當(dāng)于有
三處避難所，而每個(gè)避難所的個(gè)數(shù)都是2，因此找出的避難所個(gè)數(shù)最大是2.可想如果矩陣
中有一處是8和9,10，另一處是8和9，那么最大避難所的個(gè)數(shù)是3而不是2.
自己的實(shí)現(xiàn)思路是雙循環(huán)，每一個(gè)元素查找時(shí)判斷前后左右四個(gè)方向是不是有挨著的。
如果判斷這個(gè)值符合條件，就繼續(xù)判斷這個(gè)值得坐標(biāo)和遷移符合要求的元素的值坐標(biāo)
是不是挨著如果挨著計(jì)數(shù)器繼續(xù)增加，不挨著計(jì)數(shù)器將為0，這樣找出最大的count。
注意 尋找前一個(gè)坐標(biāo)是要初始化prei=-1，prej=-1 因此第一個(gè)符合條件的值的坐標(biāo)count++,prei=i,prej=j
以后符合條件值的坐標(biāo)要判斷該點(diǎn)坐標(biāo)和前一個(gè)點(diǎn)坐標(biāo)是否挨著再count++,且prei=i,prej=j




20170727
32位字符數(shù)，如10000000000000000000000000000000 和 00000000000000000000000000000001
左邊的數(shù)中1可以向左或向右移動(dòng)，問(wèn)向哪邊移動(dòng)次數(shù)最少可以移動(dòng)成為右邊的數(shù)字
移動(dòng)結(jié)果L 1 向左移動(dòng)一次是右面數(shù)字
0000000000000000000000000010101 0000000000000000000000000000001
左面沒(méi)法移動(dòng)成右面所以結(jié)果是 -1