(Java実装)HDOJ 1051 Wooden Sticks欲張りアルゴリズム
1658 ワード
Problem Description
(a)1本目の木材の取り付け時間は1分
(b)長さl、幅wの木材を処理した後、処理した木材の長さl'>l、w'>wに続くと、取付時間が不要となり、そうでなければ1分間の取付時間が必要となる
(c)最短実装時間のシーケンスペアを見つける
解決方法:
1.木材数nに基づいて対応するn個の木材オブジェクトを作成し、その長さと幅を初期化する
2.すべての木材を長さの昇順に並べます(長さが等しい場合、幅の広いものは後ろに並べます)
3.機械取付時間(time++)を調整し、処理配列後の未処理の長さがより長く、幅がより広く、すなわち設置時間を必要としない木材を処理済みとしてマークする
4.木材1から木材nへのループ実行手順3
(a)1本目の木材の取り付け時間は1分
(b)長さl、幅wの木材を処理した後、処理した木材の長さl'>l、w'>wに続くと、取付時間が不要となり、そうでなければ1分間の取付時間が必要となる
(c)最短実装時間のシーケンスペアを見つける
解決方法:
1.木材数nに基づいて対応するn個の木材オブジェクトを作成し、その長さと幅を初期化する
2.すべての木材を長さの昇順に並べます(長さが等しい場合、幅の広いものは後ろに並べます)
3.機械取付時間(time++)を調整し、処理配列後の未処理の長さがより長く、幅がより広く、すなわち設置時間を必要としない木材を処理済みとしてマークする
4.木材1から木材nへのループ実行手順3
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
for(int i = 0; i < a; i++){
int n = in.nextInt(); //
Wood[] woods = new Wood[n];
for(int j = 0; j < n; j++){
woods[j] = new Wood(in.nextInt(),in.nextInt());
}
Arrays.sort(woods);
int time = 0;
int nl,nw;
for(int k = 0; k <n; k++){
if(woods[k].judge == 1){ // ,
continue;
}
nl = woods[k].l;
nw = woods[k].w;
time++;
/* k , , */
for( int j = k + 1; j < n; j++ ){
if(woods[j].w >= nw && woods[j].judge == 0){
nl = woods[j].l;
nw = woods[j].w;
woods[j].setJ();
}
}
}
System.out.println(time);
}
}
}
//
class Wood implements Comparable<Wood>{
int l;
int w;
int judge = 0; //
public Wood(int l,int w){
this.l = l;
this.w = w;
}
//
public void setJ(){
this.judge = 1;
}
//
@Override
public int compareTo(Wood wood) {
//
if(l == wood.l){
return (w > wood.w)? 1:-1;
}
return (l > wood.l)? 1:-1;
}
}