SPOJ-NOTATRI : Not a Triangle

問題概要

長さL[i]の棒がN(<2000)本ある。三角形ができない(潰れてるのはOK)のは何通りあるか求める問題。

解法

長さの順にソートしておいて、短い2辺を全探索する。三角形が作れないような第3辺がいくつあるかは二分探索で求めることができる。

acceptされたコード

計算量O(N^2*log N)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 2000;
int N;
int ls[MAX_N];

bool init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", ls+i);
	}

	return N>0;
}

int solve(){
	sort(ls, ls+N);

	int ans = 0;
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			ans += N - (upper_bound(ls+j+1, ls+N, ls[i]+ls[j]) - ls);
		}
	}

	return ans;
}

int main(){
	while(init()){
		printf("%d\n", solve());
	}

	return 0;
}