NOIP模拟题 大奖赛 题解【双向搜索】【二分答案】【快速排序】

点击量：181

   这是一道双向搜索（折半搜索）的经典题目改编。

目录

题目描述

Lancelot市最近要举办大奖赛啦！住在市里的市民都十分兴奋，Morgan也不例外。他查了一下比赛的信息，发现比赛一共有N场，并且每一场的门票价格可能会不相等。Morgan留给比赛的预算是K元；他想知道，一共有多少种买票的方案，使得门票之和不超过K呢？

 

输入输出格式

输入格式：

第一行两个整数N与K，代表比赛的场数和自己的预算。 第二行N个整数Ai，代表每场比赛的门票价格。

 

输出格式：

一行一个整数，代表买票的总方案数。

 

输入输出样例

输入样例#1：

5 1000

2000 100 500 500 1000

输出样例#1：

8

说明

对于30%的数据，N<=10

 

对于60%的数据，K<=10000

 

对于100%的数据，1<=N<=40,0<k,Ai<=1000000000。

   看到数据范围，30pts的数据是可以$ 2^n$枚举的，60pts的数据是可以01背包记录方案的，然而100pts就比较极端了，两种方法均不可行，那么我们需要改变思路。

   在这种类似背包方案而背包又不可做的题目中，就可以考虑用双向搜索来使$ 2^n$的复杂度降至$ 2^{\frac{n}{2}}$，从而把整个题目的时间复杂度控制在$ O(2^{\frac{n}{2}} \log\frac{n}{2} )$（用到了二分答案）。

   双向搜索，就是把原来的一次dfs（一棵树）单调地（是一处优化）分成两棵树，使他们的最终结果进行可行性匹配，将所有情况加起来的总和就是我们要求的答案。把前mid(=n/2)小的状态先做一遍，再把后mid小的做一遍，在这过程中匹配并递归。

   做法：我们把第一次所得到的所有状态都存起来（如绿色），然后进行另一半的dfs（橙色），对每个最终状态二分匹配最优解（蓝色），在这个题中，每个状态最优解的位置就是一部分方案数。

   同时，我们可以去掉冗余状态，对于上面的图中，我们认为dfs左儿子是不选，dfs右儿子是选，也就是我们如果只选第一个物品，也要枚举到mid个状态，如：10000…（mid-1个0）。这样就无故增加了我们的工作量，我们只要在dfs的过程中进行状态的计算，就可以减少近乎一半的枚举。在每个搜索节点，如果向下搜索，一定是要经过另一个点，因为我们已经把不再经过任何点的状态处理了，这样同时也减少了代码复杂度。

   在一般的双向搜索里，我们一般找的匹配最优解更新答案，这个题要找的是最优解的位置来更新，不过只要看出双向搜索的影子，就可以向上套了。对初始状态排序是一个剪枝，而对第一次搜索后的结果排序就是必须的了，为了二分答案。数据范围比较大，记得开long long。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
long long s[1100000];
int cnts=0;
long long k,sum=0;
long long a[1100000];
int Mid,n;
int check(long long x)
{
    int l=0,r=cnts+1,mid;//二分mid不要和整体Mid搞混了
    s[cnts+1]=0x7ffffffffff;
    while(l<r)
    {
        mid=l+r>>1;
        if(s[mid]>x)
            r=mid;
        else
            l=mid+1;
    }
    return l-1;//返回最优解（前驱）的位置
}
void dfs1(int x,long long t)
{
    s[++cnts]=t;
    sum++;//每次都算一种情况
    for(int i=x+1;i<=Mid;i++)
        if(t+a[i]<=k)//可行性剪枝1
            dfs1(i,t+a[i]);
}
void dfs2(int x,long long t)
{
    sum+=check(k-t);//匹配到的全部都算一种情况
    for(int i=x+1;i<=n;i++)
        if(t+a[i]<=k)
            dfs2(i,t+a[i]);
}
int main()
{
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    std::sort(a+1,a+1+n);
    Mid=n>>1;
    s[++cnts]=0;
    for(int i=1;i<=Mid;i++)
        dfs1(i,a[i]);
    std::sort(s+1,s+cnts+1);
    for(int i=Mid+1;i<=n;i++)
        if(a[i]<=k)//可行性剪枝2
            dfs2(i,a[i]);
    printf("%lld",sum+1);
    return 0;
}