稍微简单的Meet in the middle题目

前言

先来介绍一下「Meet in the middle」是个啥

顾名思义，Meet in the middle 就是「在中间相遇」，也就是对前一半状态和后一半状态分别进行搜索，最后合并两次搜索产生的答案

这样的搜索优化（我个人认为这是优化）可以把时间复杂度开一个二次根号

思想和实现都很简单，难度主要是在合并答案这一块，一般是利用单调性进行合并

题面

题目描述

译自 CEOI2015 Day2 T1「Ice Hockey World Championship」

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入输出格式

输入格式

第一行，两个正整数 和 ，表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行， 个以空格分隔的正整数，均不超过 ，代表每场比赛门票的价格。

输出格式

输出一行，表示方案的个数。由于 十分大，注意：答案 。

输入输出样例

输入样例#1

1
2

5 1000
100 1500 500 500 1000

输出样例#1

1

8

说明

样例解释

八种方案分别是：

• 一场都不看，溜了溜了
• 价格 100 的比赛
• 第一场价格 500 的比赛
• 第二场价格 500 的比赛
• 价格 100 的比赛和第一场价格 500 的比赛
• 价格 100 的比赛和第二场价格 500 的比赛
• 两场价格 500 的比赛
• 价格 1000 的比赛

解题思路

一个很显然的思路就是暴力搜索
枚举所有的状态
最高要搜索 次

这时候 Meet in the middle 就上场了。
我们把整个区间分成 和
对这两个区间进行分别搜索，得到两个区间可选的所有方案，分别存在两个数组 和 中

如何合并答案？

首先你需要知道 upper_bound()

upper_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个大于value的值

通俗的讲，upper_bound()函数就是用来求第一个大于val的值的下标，内部使用二分查找实现
那排序肯定是没跑了（但是只需要对一个序列排序）（当然如果你两个序列都排序的话也没事，upper_bound()这里只用来查找一个序列）

枚举未排序序列的每一个元素（这里记为 ，另一个序列中的元素记为 ），显然 为「选择当前方案后剩下的钱数」，记为
对另一个序列 进行 upper_bound() 查找，找到第一个大于等于它的数的下标（这个数即为在另一个区间搜出来的「当前方案的花费」）
又因为这个区间是有序的，那么显然 upper_bound() 出来的下标之前的所有方案都是可选的（所有在它之前的方案花费都是小于等于 的，自然是可选的），更新一下答案即可

写成代码是这样的：

1
2
3
4
5
6

std::sort(b + 1, b + 1 + cntb);

for (int i = 1; i <= cnta; ++i) {
    long long int ext = m - f[i]; // 对应之前的 fafa
    ans += ((std::upper_bound(b + 1, b + 1 + cntb, ext) - b) - 1);
}

至此这道题就做完了。
还有一个小的细节：三年 OI 一场空，不开 long long 见祖宗

代码实现

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

#include <algorithm>
#include <iostream>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 40 + 10;
const int FIXED_MAX = 20 + 1;

long long int suma[(1 << FIXED_MAX) + 10], sumb[(1 << FIXED_MAX) + 10], cnta, cntb;
long long int seq[MAXN];
long long int n, m;

void Search(int l, int r, long long int sum, long long int *a, long long int &cnt) {
    if (sum > m) return;
    if (l > r) {
        a[++cnt] = sum;
        return;
    }
    Search(l + 1, r, sum, a, cnt); // don't choose
    Search(l + 1, r, sum + seq[l], a, cnt);
}

long long int mergeAnswer() {
    long long int ret = 0ll;
    std::sort(sumb + 1, sumb + 1 + cntb);
    for (int i = 1; i <= cnta; ++i) {
        ret += (std::upper_bound(sumb + 1, sumb + 1 + cntb, m - suma[i]) - sumb) - 1;
        // m - suma[i]: the money left when I choose suma[i]
    }
    return ret;
}

int main() {
    IMPROVE_IO();
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> seq[i];
    }
    int mid = (int) n >> 1;
    Search(1, mid, 0ll, suma, cnta);
    Search(mid + 1, (int) n, 0ll, sumb, cntb);
    cout << mergeAnswer() << endl;
    return 0;
}