zzuli-1758学渣的逆袭(离散化，二分，折半枚举)

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<stdlib.h>
 5 #include<string.h>
 6 #include<map>
 7 int er(int n,int m,int k);
 8 void ju();
 9 int a[5][505];
10 int b[300000];
11 int c[300000];
12 int d[300000];
13 int h[300000];
14 int aa[5];
15 int z,q,ff;
16 using namespace std;
17 map<int ,int >my;
18 int main(void)
19 {
20     int n,i,j,k,p,x1,x2,x3,x4;
21     while(scanf("%d %d %d %d",&aa[0],&aa[1],&aa[2],&aa[3])!=EOF)
22     {
23         for(i=0; i<4; i++)
24             for(j=0; j<aa[i]; j++)
25                 scanf("%d",&a[i][j]);
26         ju();
27         scanf("%d",&n);
28         int t;
29         while(n--)
30         {
31             scanf("%d",&t);
32             int coutt=0;
33             for(i=0; i<z; i++)
34             {
35                 int yy=t-b[i];
36                 coutt+=er(0,q,yy);
37 
38             }
39             printf("%d\n",coutt);
40         }
41     }
42     return 0;
43 }
44 void ju()
45 {
46     int i,j,k,p;
47     z=0;
48     q=0;
49     for(i=0; i<aa[0]; i++)//折半枚举第一组
50     {
51         for(j=0; j<aa[1]; j++)
52         {
53             b[z++]=a[0][i]+a[1][j];
54         }
55     }
56     for(i=0; i<aa[2]; i++)//折半枚举第二组
57     {
58         for(j=0; j<aa[3]; j++)
59         {
60             c[q++]=a[2][i]+a[3][j];
61         }
62     }
63     sort(c,c+q);//离散化
64     memset(d,0,sizeof(d));
65     d[0]=1;
66     ff=0;
67     h[0]=0;
68     for(i=1; i<q; i++)
69     {
70         if(c[i]!=c[i-1])//去重
71         {
72             ff++;
73         }
74         d[ff]++;//离散化时将原来的点转为对应的点并记录出现个数
75         h[i]=ff;
76     }
77 
78 }
79 int er(int n,int m,int k)//二分找点
80 {
81     int i=(n+m)/2;
82     if(n>m)
83     {
84         return 0;
85     }
86     if(c[i]==k)
87     {
88         return d[h[i]];
89     }
90     else if(c[i]>k)
91     {
92         return er(n,i-1,k);
93     }
94     else return er(i+1,m,k);
95 }