PDF (English)

Statistics

Forum

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.

题解

二分查找题，题意就是从集合中选长度拼三角形。其实就是暴力枚举两个边，然后第三个便就可以二分查找的方法从集合中找出来。当然集合要事先排好序。最后最坑爹的一点是数据int过不去，需要全部改成longlong。其他的就没什么了。大部分都是相同的代码。

代码示例

/****
	*@author    Shen
	*@title     LightOj 1307
	*/

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; typedef long long int64; const int maxN = 2005; int64 a[maxN]; int t, tt; int n; int64 Bsearch_lower_bound(int64 x) { int64 l = 0, r = n - 1, mid = 0; while (l <= r) { mid = (l + r) >> 1; if (a[mid] < x) l = mid + 1; else r = mid - 1; } return l; } int64 Bsearch_upper_bound(int64 x) { int64 l = 0, r = n - 1, mid = 0; while (l <= r) { mid = (l + r) >> 1; if (a[mid] <= x) l = mid + 1; else r = mid - 1; } return l; } void solve() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); int64 cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { int64 x = a[i] - a[j]; int64 y = a[i] + a[j]; int64 t1 = Bsearch_lower_bound(x + 1); int64 t2 = Bsearch_upper_bound(y - 1); cnt += (t2 - t1); if ((i >= t1) && (i <= t2)) cnt--; if ((j >= t1) && (j <= t2)) cnt--; } } printf("Case %d: %d\n", ++tt, cnt / 3); } int main() { scanf("%d", &t); while (t--) solve(); return 0; }