Lightoj 1307 二分

题目：

You are given N sticks having distinct lengths; you have to form some triangles using the sticks. A triangle is valid if its area is positive. Your task is to find the number of ways you can form a valid triangle using the sticks.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer N (3 ≤ N ≤ 2000). The next line contains N integers denoting the lengths of the sticks. You can assume that the lengths are distinct and each length lies in the range [1, 10⁹].

Output

For each case, print the case number and the total number of ways a valid triangle can be formed.

Sample Input

3

5

3 12 5 4 9

6

1 2 3 4 5 6

4

100 211 212 121

Sample Output

Case 1: 3

Case 2: 7

Case 3: 4

题意：给你若干根棍子，问能拼出多少多少个三角形。

方法：二分查找。

C++ STL中的upper_bound,lower_bound能减轻不少负担。关于lower_bound,upper_bound的介绍，见百度。

点击打开链接

代码：

//By Sean Chen #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int t,n,stick[2005]; int cmp(int a,int b) { return a<b; } int main() { scanf("%d",&t); for (int Case=1;Case<=t;Case++) { printf("Case %d: ",Case); scanf("%d",&n); for (int i=0;i<n;i++) scanf("%d",&stick[i]); sort(stick,stick+n,cmp); int ans=0; for (int i=0;i<n-2;i++) { for (int j=i+1;j<n-1;j++) { int pos=lower_bound(stick+j,stick+n,stick[i]+stick[j])-stick; if(j!=pos) ans=ans+(pos-j-1); } } printf("%d\n",ans); } return 0; }