首页 > 代码库 > 折半枚举（双向搜索）

折半枚举（双向搜索）

2024-07-29 22:51:55   211人阅读

各有n个整数的四个数列A、B、C、D。要从每个数列中各取一个数，使四个数的和为0。求出这样组合的个数。

输入

n = 6

A = { -45, -41, -36, -36, 26, -32 }

B = { 22, -27, 53, 30, -38, -54 }

C = { 42, 56, -37, -75, -10, -6 }

D = { -16, 30, 77, -46, 62, 45 }

从4个数列中选择共有n4种情况，全部判断一遍不可行。不过将它们对半分成AB和CD再考虑，就可以快速解决了。从2个数列中选择的话只有n2种组合，所以可以进行枚举。先从A、B中取出a、b后，为使总和为0需要从C、D中取出c + d = -(a + b)。因此先将从C、D中取数字的n2种方法全都枚举出来，将这些和排序，进行二分搜索。这个算法复杂度为O(n2logn)。

 1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 using namespace std; 5  6 #define MAX_N 1000 7  8 int n; 9 int A[MAX_N], B[MAX_N], C[MAX_N], D[MAX_N];10 int CD[MAX_N * MAX_N];    //C和D中数字的组合方法11 12 void solve()13 {14     //枚举从C和D中取出数字的所有方法15     for (int i = 0; i < n; i++)16     {17         for (int j = 0; j < n; j++)18         {19             CD[i*n+j] = C[i] + D[j];20         }21     }22     sort(CD, CD+n*n);23     long long res = 0;24     for (int i = 0; i < n; i++)25     {26         for (int j = 0; j < n; j++)27         {28             int cd = -(A[i] + B[j]);29             //取出C和D中和为cd的部分30             res += upper_bound(CD, CD+n*n, cd) - lower_bound(CD, CD+n*n, cd);31         }32     }33     printf("%lld\n", res);34 }35 36 37 int main()38 {39     cin >> n;40     for (int i = 0; i < n * 4; i++)41     {42         switch (i / 6)43         {44         case 0:45             cin >> A[i % 6];46             break;47         case 1:48             cin >> B[i % 6];49             break;50         case 2:51             cin >> C[i % 6];52             break;53         case 3:54             cin >> D[i % 6];55             break;56         default:57             break;58         }59     }60     solve();61     return 0;62 }

 

折半枚举（双向搜索）


联系
我们