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; }