选择客栈(巧妙)

题面:https://www.luogu.com.cn/problem/P1311

丽江河边有

两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过

他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过

$样例:$

写出这题还是比较得意的，虽然中途下载了测试数据，不过思想是自己的。

①自己的思想O(nk)

Ⅰ.我们这样想，如果一个客栈的右边(包括自己)都是花费大于P的，那么这个客栈的右边一定不存在和这个客栈匹配的。

Ⅱ.如果某个客栈 i 和右边的同色客栈 j 符合条件的话，那么他们之间肯定存在一个花费低于P的客栈

Ⅲ.在Ⅱ的基础上， j 右边的同色客栈一定能和i组成符合条件的。

Ⅳ.综上所诉，我们只关系客栈右边第一个价值符合条件的客栈位置，以及该符合条件的客栈(包括该客栈)右边有几个同色客栈。

②实现

Ⅰ.客栈右边第一个价值低于P客栈的位置，我们直接倒序枚举。

初始令ans=-1表示右边没有合适的客栈了

然后发现一个符合条件的客栈就更新ans的位置

int ans=-1;//表示没有 
for(int i=n;i>=1;i--)
{
    if(hua[i]<=p)    ans=i;//更新 
    jin[i]=ans;
}

Ⅱ.对于颜色统计，仍然倒序枚举，用vis数组统计颜色情况。

sumn [ i ] [ j ] 表示在 i 客栈后面(包括 i 客栈)有 j 颜色的客栈多少个

for(int i=n;i>=1;i--)
{
    vis[color[i]]++;//统计当前颜色 
    for(int j=0;j<=k;j++)
        sumn[i][j]=vis[j];//把所有颜色装进去 
}

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=200009;
int n,k,p;
int color[maxn],hua[maxn],vis[59];
int jin[maxn];//从i往后,最快遇到得廉价酒馆
int sumn[maxn][59];//从i往后，不包括i与i同色得酒馆 
int main()
{
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++)    scanf("%d%d",&color[i],&hua[i]);
    int ans=-1;
    for(int i=n;i>=1;i--)
    {
        if(hua[i]<=p)    ans=i;
        jin[i]=ans;
        vis[color[i]]++;
        for(int j=0;j<=k;j++)
            sumn[i][j]=vis[j];
    }
    int cnt=0;
    for(int i=1;i<=n;i++)//O(n)扫一遍
    {
        if(jin[i]==-1)    continue;
        //右边没有价值更低的客栈了,continue 
        cnt+=sumn[jin[i]][color[i]];
        if(jin[i]==i)    cnt--;
        //如果自己就是距离最近的廉价客栈
        //那么sumn[jin[i]][color[i]]多算了一次
        //自己是不可以和自己匹配的 
    } 
    cout<<cnt;
}

View Code

不过，令人伤心的是，还有更快的O（n）算法。

箭头代表该客栈是小于花费P的客栈

那么，当我们枚举到第二个客栈时，发现这是在当前枚举过程中最后出现的一个符合花费的客栈，我们把他的下标记作 t

所以后面的客栈总可以和第二个客栈前面的同色客栈形成一对

然后我们枚举到第四个客栈时，更新t

从第四个客栈开始起，所有后续客栈都可以和4之前的同色客栈形成一对,而不是仅仅和2之前的同色客栈形成一对。

所以奉上代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=500009;
int n,k,p,last[maxn],sumn[maxn];
int color,price,vis[59];
//vis记录颜色 
int main()
{
    cin>>n>>k>>p;
    int ans=0,now;
    for(int i=1;i<=n;i++)
    {
        cin>>color>>price;
        if(price<=p)    now=i;
        //now记录目前最后符合条件的客栈编号 
        if(now>=last[color])//如果大于上一个颜色出现的位置
            sumn[color]=vis[color];//那么不仅仅是2之前的，现在是4之前的 
        last[color]=i;//最后一次出现在i
        ans+=sumn[color];
        vis[color]++; 
    }
    cout<<ans; 
}

View Code