题解 P1311 【选择客栈】

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