题解：P1311 [NOIP2011 提高组] 选择客栈

bravo11111111 · 2025-01-13 16:35:23 · 题解

解题想法

这道题我们如果枚举每两个客栈，时间肯定是要超的。但这到题要求选两个颜色相同的客栈，我们可以枚举每种颜色的客栈,时间复杂度为 O(k\times n)。

解题思路

我们不难可以发现，当两个颜色相同客栈中间，有满足最小花费小于 p 的客栈时，那么两个客栈中后面的那个客栈一定能和前面的那个客栈及其他前面所有与他颜色相同客栈配对。了解这点，就可以做出这道题。

AC代码

#include<bits/stdc++.h>
using namespace std;
long  long n, k,p,a[200005],ans,b[200005],sum,num,ma,x,nu;
int main(){
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    for(int i=0;i<k;i++){//枚举颜色
    long long t=0,answer=0,mi=1e18;
        for(int j=1;j<=n;j++)
        {
            mi=min(mi,b[j]);
            if(a[j]==i){//颜色相同
                t++;
                if(t>1)
                    if(mi<=p)
                        answer=t-1;//更新最前面可以与它配对的客栈
                    mi=b[j];
                    ans+=answer;//相加
                }
            }
        }
    printf("%d",ans);
    return 0;
    }