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

作者: wjyyy 分类: 二分,双向搜索,快速排序,搜索,解题报告 发布时间: 2018-06-21 17:41

点击量:17

 

   这是一道双向搜索(折半搜索)的经典题目改编

 

题目描述

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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */