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

WsW_ · 2025-01-10 22:29:27 · 题解

思路

枚举靠左边的那个客栈，考虑对于左边的客栈为 i 时右边客栈有多少种选择。
发现如果没有咖啡店这个限制，那么答案就是 i+1\sim n 之间有多少个客栈的色调为 a_i。这可以通过前缀和快速求出。
但是有咖啡店这个限制，也就是两个客栈之间至少要有一个咖啡店的消费小于 p。我们发现，如果选择在第 t 个咖啡店喝咖啡，那么右边客栈的选择数就是 t\sim n 之间有多少个客栈的色调为 a_i。容易发现，越是选择靠左的咖啡店，右边客栈的选择数越多，所以我们直接选择最靠左的咖啡店。
然后这道题就变成了查询在 i 右边且最靠左的咖啡店位置 t 是多少，以及 t\sim n 之间有多少个客栈色调为 a_i。第一个查询可以通过前缀最值求出，第二个查询可以通过前缀和求出。
注意，两个人不能选择同一个客栈，当 t=i 时第二个查询的区间就变成了 t+1\sim n。

时间复杂度为 O(nk)。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=2e5+5;
int n,k,p;
ll ans;
int a[maxn],b[maxn];
int sum[maxn][55];
int c[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>k>>p;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];

    for(int i=n;i>0;i--)
        for(int j=0;j<k;j++){
            sum[i][j]=sum[i+1][j]+(a[i]==j);
            c[i]=(b[i]<=p?i:c[i+1]);
        }

    for(int i=1;i<=n;i++)
        ans+=sum[(c[i]==i?c[i]+1:c[i])][a[i]];//要特判

    cout<<ans;
    return 0;
}