题解 P1311 【选择客栈】

这道题,一看就知道暴力枚举(其实我看了半天完全不知道有啥好方法咋做,好像就只要暴力),我们看数据范围,n<=200000,如果朴素枚举(O(n^3))的话肯定会爆炸,然后一开始我是想了个略有优化的枚举,时间复杂度能勉强降到O(n^2),然后就拿了60(看数据范围,第6个点应该是卡常过的),后来发现如果改一下循环可以降到近乎O(n)的,不过实际上这个枚举量取决于数据,比较奇怪(玄学),具体见代码,顺便给出原来O(n^2)的代码

#include<cstdio>
using namespace std;
const int N=200010;
int cl[103][N],dop[N];//cl数组用来记录一个色调上的所有客栈,这个数组差不多占75MB,所以不会爆空间
int main()//dop数组用来记录咖啡馆的最低费用在p以下的所有咖啡馆
{
    int i,j,m,n,p,k,v,c,l=0,s=0;
    scanf("%d%d%d",&n,&k,&p);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&c,&v);
        cl[c][++cl[c][0]]=i;//将这个编号扔入它所对应的位置
        if(v<=p)
            dop[++l]=i;//把满足条件的客栈扔进去
    }
    for(j=0;j<=k;j++)//按色调枚举
    {
        v=1;//这个东西贼重要,我的优化主要靠它
        for(c=1;c<cl[j][0];c++)//枚举同一种色调的客栈,因为输入是有序的,所有数组也是有序的
            for(i=v;i<=l;i++)//枚举满足最低消费条件的客栈
                if(dop[i]>=cl[j][c])//如果这个满足条件的客栈的编号不小于目前c所枚举的客栈编号,就说明可能存在住宿方案
                {
                    s+=cl[j][0]-c;//先把所有可住宿的方案加进去
                    v=i;//重点在这,如果没有这个v,这个枚举也只能A6个点,在这我们注意到现在这个编号是恰好大于等于c下标所对的客栈编号,所有前面的编号是不需要枚举的,因此这个v可以大大减少时间(其实这个v是我在调试的时候想到的,当时觉得调试太慢了,然后就想到了这个……)
                    m=c+1;//接下来我们要减去不符合条件的住宿方案,因为目前这个dop可能大于c+1下标对应的客栈编号,这样是不符合的
                    while(dop[i]>cl[j][m]&&m<=cl[j][0])//同时注意防止m越界,我就被坑了半个小时……
                    {
                        m++;
                        s--;//减去不符合的方案
                    }
                    break;//因为题目要的是住宿方案,所以只要有一个咖啡馆满足条件就可以了,然后就break掉循环
                }
    }
    printf("%d",s);
    return 0;
}

下面是我一开始的勉强能达到O(n^2)的枚举,下面的数组含义均以上相同

for(i=0;i<=k;i++)
    for(j=1;j<=cl[i][0];j++)
        for(c=j+1;c<=cl[i][0];c++)//枚举每个区间,当时没注意只要比前面的客栈编号大就可以,然后就在那傻愣愣的枚举区间
            for(m=1;m<=l;m++)
                if(dop[m]>=cl[i][j])
                {
                    if(dop[m]<=cl[i][c])//满足条件就加一方案
                        s++;
                    break;//意义同上
                }

总之,这道题以我一蒟蒻的实力真的不知道什么好的算法,看题目标签是递推&栈,but蒟蒻表示完全不能理解= =,怎么递推?栈又和这题有啥关系(抓狂ing)!反正还好这题是线性,好枚举,然后本蒟蒻竟然暴力A(其实一开始我只是打算就拿6个点算了,后来调试加了v没想到就A了,真·一脸懵逼),现在翻了题解,原来这题是可以用线段树的(可蒟蒻不会啊……),又看各路大佬展现神奇的前缀啥的来O(n)枚举,蒟蒻表示还是%%%。坐等NOIP爆零


发表于 2017-10-31 20:57:00 in 题解