二分求解三角形 stl的应用涉及范围的二分查找可以先求上界再算下界，结果即上界减下界

二分

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

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, 10⁹].

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

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <math.h>
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 LL a[2000+5];
 9 int n;
10 
11 int Binary_search(int x)
12 {
13     int l = 0,r = n-1;
14     while(l<=r)
15     {
16         int mid = (l+r)/2;
17         if(a[mid] == x)
18             return mid;
19         else if(a[mid] > x)
20             r= mid-1;
21         else
22             l = mid +1;
23     }
24     return l;
25 
26 }
27 
28 int main()
29 {
30     int T;
31     cin>>T;
32     int flag = 0;
33     while(T--)
34     {
35 
36         cin>>n;
37         for(int i = 0; i < n; i++)
38             scanf("%lld",&a[i]);
39         sort(a,a+n);
40         int ans = 0;
41         for(int i = 0; i < n-1; i++)
42             for(int j = i+1; j < n; j++)
43             {
44                 LL sum = a[i] + a[j];
45                 LL cha = abs(a[j] - a[i]);
46 
47                 int up = Binary_search(sum)-1;
48                 if(up <= j)
49                     continue;
50                 int low = Binary_search(cha);
51                 if(low < j)
52                     low = j;
53                 ans +=  (up-low);
54 
55 
56             }
57 
58         cout<<"Case "<<++flag<<": "<<ans<<endl;
59 
60     }
61     return 0;
62 }

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <math.h>
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 LL a[2000+5];
 9 int n;
10 
11 int Binary_search(int x)
12 {
13     int l = 1,r = n;
14     while(l<r)
15     {
16         int mid = (l+r)/2;
17         if(a[mid] == x)
18             return mid;
19         else if(a[mid] > x)
20             r= mid;
21         else
22             l = mid +1;
23     }
24     return l;
25 
26 }
27 
28 int main()
29 {
30     int T;
31     cin>>T;
32     int flag = 0;
33     while(T--)
34     {
35 
36         cin>>n;
37         for(int i = 0; i < n; i++)
38             scanf("%lld",&a[i]);
39         sort(a,a+n);
40         int ans = 0;
41         for(int i = 0; i < n-1; i++)
42             for(int j = i+1; j < n; j++)
43             {
44                 LL sum = a[i] + a[j];
45                 LL cha = abs(a[j] - a[i]);
46 
47                 int up = Binary_search(sum)-1;
48                 if(up <= j)
49                     continue;
50                 int low = Binary_search(cha);
51                 if(low < j)
52                     low = j;
53                 ans +=  (up-low);
54 
55 
56             }
57 
58         cout<<"Case "<<++flag<<": "<<ans<<endl;
59 
60     }
61     return 0;
62 }

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <math.h>
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 LL a[2000+5];
 9 int n;
10 
11 int main()
12 {
13     int T;
14     cin>>T;
15     int flag = 0;
16     while(T--)
17     {
18 
19         cin>>n;
20         for(int i = 0; i < n; i++)
21             scanf("%lld",&a[i]);
22         sort(a,a+n);
23         int ans = 0;
24         for(int i = 0; i < n-1; i++)
25             for(int j = i+1; j < n; j++)
26             {
27                 LL sum = a[i] + a[j];
28                 LL cha = abs(a[j] - a[i]);
29 
30                 int up = upper_bound(a+j+1,a+n,sum)-a;
31 
32 
33                 int low = lower_bound(a+j+1,a+n,cha)-a;
34 
35                 ans +=  (up-low);
36 
37 
38             }
39 
40         cout<<"Case "<<++flag<<": "<<ans<<endl;
41 
42     }
43     return 0;
44 }

View Code

二分求解 三角形 stl的应用 涉及范围的二分查找可以先求上界再算下界，结果即上界减下界

二分求解三角形 stl的应用涉及范围的二分查找可以先求上界再算下界，结果即上界减下界