折半搜索(meet in the middle)算法

洛谷模板题：https://www.luogu.com.cn/problem/P4799

ac代码：

时间复杂度：

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include<set>
 8 #include
 9 #include
10 #include
11 #include<string>
12 #define ll long long
13 #define ull unsigned long long
14 #define inf 0x3f3f3f3f
15 #define inff 0x7fffffff
16 #define int long long
17 using namespace std;
18 const int N = 100 + 10;
19 
20 int a[N];
21 int n, m;
22 vector<int>v1, v2;
23 
24 void dfs(int st, int en, int sum, vector<int>& v) {
25     
26     if (sum > m) return;
27     if (st > en) {
28         v.push_back(sum);
29         return;
30     }
31     dfs(st + 1, en, sum + a[st], v);
32     dfs(st + 1, en, sum, v);
33 
34 }
35 
36 signed main() {
37 
38     //int n, m;
39     cin >> n >> m;
40     for (int i = 1; i <= n; i++) cin >> a[i];
41     dfs(1, n / 2, 0, v1);
42     dfs(n / 2 + 1, n, 0, v2);
43     sort(v1.begin(), v1.end());
44     int ans = 0;
45     for (int i = 0; i < v2.size(); i++) {
46         int x = upper_bound(v1.begin(), v1.end(), m - v2[i]) - v1.begin();
47         ans += x;
48     }
49     cout << ans << "\n";
50 
51     return 0;
52 }

还有一道题：https://ac.nowcoder.com/acm/contest/33540/I?&headNav=acm

这道题是二分答案+折半搜索，也差不多是道模板题

代码：

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include<set>
 8 #include
 9 #include
10 #include
11 #include<string>
12 #define ll long long
13 #define ull unsigned long long
14 #define inf 0x3f3f3f3f
15 #define inff 0x7fffffff
16 #define int long long
17 using namespace std;
18 const int N = 100 + 10;
19 
20 int a[N];
21 int b[N];
22 int n, m, k, w;
23 vector<int>v1, v2;
24 
25 void dfs(int st, int en, int sum, vector<int>& v) {
26     
27     if (sum > m) return;
28     if (st > en) {
29         v.push_back(sum);
30         return;
31     }
32     dfs(st + 1, en, sum + a[st] + (b[st] * w), v);
33     dfs(st + 1, en, sum, v);
34 
35 }
36 
37 signed main() {
38 
39     //int n, m, k;
40     cin >> n >> m >> k;
41     for (int i = 1; i <= n; i++) cin >> a[i];
42     for (int i = 1; i <= n; i++) cin >> b[i];
43 
44     int ans_f = 0;
45     int l = 0;
46     int r = 1e9 + 10;
47     while (l <= r) {
48 
49         v1.clear();
50         v2.clear();
51         w = (l + r) >> 1;
52         int ans = 0;
53         dfs(1, n / 2, 0, v1);
54         dfs(n / 2 + 1, n, 0, v2);
55         sort(v1.begin(), v1.end());
56         for (int i = 0; i < v2.size(); i++) {
57             int x = upper_bound(v1.begin(), v1.end(), m - v2[i]) - v1.begin();
58             ans += x;
59         }
60         if (ans < k) {
61             r = w - 1;
62         }
63         else {
64             l = w + 1;
65             ans_f = w;
66         }
67 
68     }
69     cout << ans_f << "\n";
70 
71     return 0;
72 }
二分答案折半搜索

相关

[模板]二分答案

代码源div1 每日一题 二分答案

标签