PKU 3663 Costume Party
http://poj.org/problem?id=3663
長さn<=20000の数列が与えられる。この時この要素の中から2組取ってきて、その和がs以下になるような組み合わせはいくつあるか、というような問題。
ソートして2分探索。O(nlogn)
int in[20000]; main(){ int n,s; cin>>n>>s; rep(i,n)cin>>in[i]; sort(in,in+n); int ans=0; rep(i,n-1){ if(in[i]+in[i+1]>s)break; ans+=upper_bound(in+i+1,in+n,s-in[i])-in-i-1; } cout<<ans<<endl; }