[Algorithm] 🧗白準2217ロープ

7102 ワード
白駿 グリディ テキストリンク

0、問題


N(1≦N≦100000)本のロープがあります.このロープでこのような物体を持ち上げることができます.各ロープの太さや長さが異なると、持ち上げられる物体の重量が異なる可能性があります.
しかし、複数のケーブルを並列に接続すると、各ケーブルに必要な重量を区分することができる.k本のロープを用いて重量wの物体を持ち上げると、各ロープは平均してw/kの重量を必要とする.
各ケーブルに関する情報を取得する場合は、持ち上げられる物体の最大重量を解くプログラムを作成します.すべてのロープを使う必要はなく、何本かのロープを任意に選ぶことができます.
入力
最初の行は整数Nを与える.次のN本のロープには、各ロープが耐えられる最大重量が与えられる.この値は10000を超えない自然数です.
しゅつりょく
最初の行に答えを印刷します.

1.アイデア


1)ケーブルを昇順に並べる
2) 1,2, ... wの最大値を検索(k単位)

2.コア解答


1)ケーブルを昇順に並べる
Arrays.sort(arr);
2) 1,2, ... wの最大値を検索(k単位)
for(int i=0; i<k; i++) 
			w = Math.max(w, (k-i)*arr[i]);

3.コード

import java.io.*;
import java.util.Arrays;
public class Greedy_2 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int k = Integer.parseInt(br.readLine());
		int w = -1;
		int arr[] = new int[k];
		
		for(int i=0; i<k; i++) 
			arr[i] = Integer.parseInt(br.readLine());		
		
		Arrays.sort(arr);
		
		for(int i=0; i<k; i++) 
			w = Math.max(w, (k-i)*arr[i]);
		
		System.out.println(w);
	}
}

4.結果



成功～
ch 11集合フレームワーク
Serializable VS. Parcelable