【lightoj1307】Counting Triangles

﹏ヽ暗。殇╰゛Y 2022-07-17 01:43 43阅读 0赞

J - J 圆周率用acos(-1.0) 使用longlong

**Time Limit:**2000MS **Memory Limit:**32768KB **64bit IO Format:**%lld & %llu

Submit [Status][] [Practice][] [LightOJ 1307][] [![12x12_uDebug.png][]uDebug][12x12_uDebug.png_uDebug]

Description

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, 109\]**.

Output

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

Sample Input

3 12 5 4 9

1 2 3 4 5 6

100 211 212 121

Sample Output

Case 1: 3

Case 2: 7

Case 3: 4

比赛时没TLE豁然开朗，原来用二分可以轻松解决超时问题，看来二分更多的时候是用来优化程序的，我喜欢这种题。

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int a[2005];
    bool judge(int mid,int i,int j) {
    	if(a[i]+a[j]>a[mid]&&a[mid]-a[i]<a[j]) {
    		return true;
    	}
    	return false;
    }
    int main() {
    	int T,p=0;
    	scanf("%d",&T);
    	while(T--) {
    		int n;
    		scanf("%d",&n);
    		for(int i=0; i<n; i++) {
    			scanf("%d",&a[i]);
    		}
    		sort(a,a+n);
    		int ans=0;
    		for(int i=0; i<n; i++) {
    			for(int j=i+1; j<n; j++) {
    				int cnt=0;
    				int l=j+1,r=n-1;
    				while(l<=r) {
    					int mid=l+r>>1;
    					if(judge(mid,i,j)) {
    						cnt=mid;
    						l=mid+1;
    					} else {
    						r=mid-1;
    					}
    				}
    				if(cnt)
    					ans=ans+cnt-j;
    			}
    		}
    		printf("Case %d: %d\n",++p,ans);
    	}
    	return 0;
    }

[Status]: http://acm.hust.edu.cn/vjudge/contest/130068#status//J/0
[Practice]: http://acm.hust.edu.cn/vjudge/problem/25958
[LightOJ 1307]: http://acm.hust.edu.cn/vjudge/problem/25958/origin
[12x12_uDebug.png]: http://acm.hust.edu.cn/vjudge/images/12x12_uDebug.png
[12x12_uDebug.png_uDebug]: https://www.udebug.com/LOJ/1307