三角形

三角形(プログラミングコンテストチャレンジブックp21)

n本の棒があり、棒iの長さは。それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えている。最大の周囲はいくら？ただし、三角形が作れない場合は、0と答える。
制約

アルゴリズム

三角形を作ることができる必要十分条件(三角不等式)

最大辺長 < 他の２辺の長さの和

を使って、三角形が生成可能かを判定しながら、３重ループをまわす。なので、これで十分だが、O(n log n)で解ける。

ソート済みのを

とすると求めるのは、。
iを決めたとして、j,kをの範囲で探せばよい。
を最大化のみを考えると、j=i+1, j=i+2とすればよい。
そして、を満たさないのであれば、どんなj,kを選んでもを満たすことはない。
従って、ソートしといて大きい方から連続する3辺について、三角不等式を満たすものを探せばよい
と思う...

コード

import java.util.*;
public class triangle {
	static Scanner scanner;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new triangle();
	}
	triangle(){
		int n = scanner.nextInt();
		Integer[] a = new Integer[n];
		for(int i = 0; i < n; i++)
			a[i] = scanner.nextInt();
		System.out.println( "solve 1 = " + solve1(n, a) );
		System.out.println( "solve 2 = " + solve2(n, a) );
	}
	
	// O(n^3)
	int solve1(int n, Integer[] a){
		int ans = 0;
		// i < j < k として、重複を避ける
		for(int i = 0; i < n; i++){
			for(int j = i+1; j < n; j++){
				for(int k = j+1; k < n; k++){
					int sum = a[i] + a[j] + a[k];
					int long_edge = Math.max(a[i], Math.max(a[j], a[k]));
					
					if(long_edge < sum - long_edge ) ans = Math.max(ans, sum);
				}
			}
		}
		return ans;
	}
	// O(n log n)
	int solve2(int n, Integer[] a){
		int ans = 0;
		Arrays.sort(a, new Comparator<Integer>(){
			@Override
			public int compare(Integer o1, Integer o2){ return o2.compareTo(o1); }
		});
		for(int i=0; i<n-2; ++i){
			if( a[i] < a[i+1] + a[i+2] ){
				ans = a[i] + a[i+1] + a[i+2];
				break;
			}
		}
		return ans;
	}
}