By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 分析：

题目大意：

　　给4组数据，每组数据n个数，求从每组抽一个数和为0的组数

分析：

  • 先把a+b存到数组C，c+d存到数组D。
  • 枚举a+b的值,在c+d的值里二分查找-(a+b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 16000010;

int c[N], d[N];
int a[4000][4];
int counts;

void finds(int a[], int L, int r, int k)//L是上界，r是下界
{
    int left = L, right = r;
    int x;
    while(left <= right){
        x = (left + right) >> 1;
        if(a[x] < k)    left = x + 1;
        else if(a[x] > k) right = x - 1;
        else{
	    //注意这个版本的二分查找找到的值是中间的那个，也许左右两边有和他相等的值
            for(int i = x; i < r; i++){
                if(a[i] == k){
                    //printf("key: %d \nresult: %d \n\n", k, a[i]);
                    counts++;
                }else{
                    break;
                }
            }
            for(int i = x - 1; i >= 0; i--){
                if(a[i] == k){
                    counts++;
                }else{
                    break;
                }
            }
            return ;
        }
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    int n, T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 4; j++){
                scanf("%d", &a[i][j]);
            }
        }
        //将a+b和c+d分别放入两个数组里
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                c[i*n + j] = a[i][0] + a[j][1];
                d[i*n + j] = a[i][2] + a[j][3];
            }
        }
        sort(d, d + n * n);
        counts = 0;
        int nn = n * n;
        //枚举a+b的值在c+d的值里二分查找-(a+b)
        for(int i = 0; i < nn; i++){
            finds(d, 0, nn, -c[i]);
        }
        printf("%d\n", counts);
        if(T)
            puts("");
    }
    return 0;
}
Contents
  1. 1. 题目大意：
  2. 2. 分析：