选择客栈1311解题报告

· · 题解

这个题目真的快把我想死了。。。。

其实这个题目本身并不难，一开始我就想到了暴力求解，但是像我这种追求AC率的人不到考试是不会这样做的，于是我就开了个小号(AC率出现了特殊情况).

所以为了AC,我就要去降低其时间复杂度,于是通过观察发现,之前可以去的后面的都可以去,但是要记录当前客栈可以去的最近客栈(费用最低),于是我就弄了个数组ct[i][2],ct[i][0]用来储存该颜色可以去的客栈,ct[i][1]用了储存因费用问题(他们旅游怎么不多带点钱呢!?)而不能去的客栈,于是问题似乎就解决了.但是!但是,我错了...因为我一开始没弄好顺序的问题(这个问题真的是想死我了),就错了几次(还好是小号//手动滑稽),之后我自己弄了一个数据就出来了
这个数据是这样的:7 2 3 \0 5\1 3\0 2\0 4\0 2\1 4\1 2
如果直接在for下就让ct[color[i]][0]加1的话会有一个顺序问题,本来从3到1只能有一次,但是这样会让它多加一次,于是在pr<=p时就要先加上可以加的(t+=ct[color[i]][0]]),在把这个客栈加入可以去的客栈(ct[color[i]][0]++),这样问题就解决了
(如果还不清楚就自己模拟一下,我一开始是直接把ct[color][0]++放在for下的,下面的t+=ct[color[i]][0],ct[color][0]++与else是没有的)

下面是参考程序(虽然很弱,但至少对了):

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,p,k,ct[52][2],color[200020],pr[200020],t,now,cos[52],all,f[52];
//color是颜色,ct[i][0]是i可以去的客栈数量,ct[i][1]是i因费用问题不能去的客栈数量,cos是颜色种类(怕题目太坑,把color弄成500什么的);
//f一开始是记录颜色种类时用的,之后其实没什么用,我只是不想删→_→ ;
int main()
{
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&color[i],&pr[i]);
        if(!f[color[i]]){f[color[i]]=1;cos[++all]=color[i];}//记录颜色种类; 
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    {

        if(pr[i]<=p)
        {
            for(int j=1;j<=all;j++)//递推; 
            {
                ct[cos[j]][0]+=ct[cos[j]][1];//把之前因费用而不能去的地方加上; 
                ct[cos[j]][1]=0;//清空 
            }t+=ct[color[i]][0]; 
            ct[color[i]][0]++;//注意!注意!!注意!!!这两行的顺序必须如此!!!!
        }
        else {ct[color[i]][1]++;t+=ct[color[i]][0];}//注意!注意!!注意!!!这两行的顺序必须如此!!!! 
        //详情看上面的说明; 
    }
    printf("%d",t);
}