题解 P1311 【选择客栈】

莫舍尼数列 · 2018-11-01 20:46:39 · 题解

先讲暴力思路：

暴力得70分

对于每一种颜色，都对于当前颜色，下一个与其相同的颜色的客栈的地址（位置）。

然后枚举每一种颜色，再枚举每一对颜色相同的客栈，看看他们之间有没有咖啡厅。如果有就总数++；

对于查询有没有咖啡厅，可以用一个类前缀和数组s[i]记录在i之前有多少个符合条件的咖啡厅。这样到时候后减前就可以查询到底有没有，就不用遍历数组了。

这样复杂度会爆炸。

随后是改了三行的代码，就AC了。考虑任意两对颜色相同的客栈，如果靠前一点的客栈与靠后一点的客栈符合条件，那（这个靠前一点的客栈）与（这个靠后一点的客栈往后的客栈）一定都满足条件（括号帮你们画好了断句，免得看不懂233我经常在这种长句子里懵逼），为何还要去一一判断呢？只需加上他们的数目就好了。至此AC。

这么简单的题，怎么可能是提高难度呢~~~

AC代码：```cpp

include <iostream>

int n,k,p; struct data { int num; int nex=-1; }a[200001]; int first[101]={0}; int total[101]={0}; int s[200001]={0}; int cnt=0;

int main() { using namespace std;

cin>>n>>k>>p;
for(int i=1;i<=n;i++)
{
    cin>>a[i].num;
    if(first[a[i].num]==0)
        first[a[i].num]=i;
    total[a[i].num]++;

    int tmp;
    cin>>tmp;
    if(tmp<=p)
        s[i]=s[i-1]+1;
    else
        s[i]=s[i-1];
}

for(int e=0;e<=k-1;e++)
{
    int now;

    for(int i=1;i<=total[e]-1;i++)
    {
        if(i==1)
            now=first[e];

        for(int j=now+1;true;j++)
            if(a[j].num==e)
            {
                a[now].nex=j;
                now=j;
                break;
            }       
    }
}

for(int e=0;e<=k-1;e++)
{
    int here=1;
    for(int i=first[e];a[i].nex!=-1;i=a[i].nex,here++)
    {
        int location=here;
        for(int j=a[i].nex;j!=-1;j=a[j].nex,location++)
            if(s[j]-s[i-1]!=0)
            {
                cnt+=(total[e]-location);
                location++;
                break;
            }
    }
}

cout<<cnt;

return 0;

}