P1311 选择客栈

题面:https://www.luogu.org/problem/P1311

本题先考虑暴力,即枚举每一个客栈,找后面第一个与当前客栈相同颜色且满足最低消费不超过p的客栈,然后统计在此客栈后有多少个与当前颜色相同的客栈,累计入答案即可.
那么正解做法也就自然而然地出来了,即枚举每一个客栈,找一个与之最近的满足条件的咖啡店p1,然后判断上一个与当前客栈相同颜色的客栈是否在p1之前,
如果在就将当前客栈的颜色出现次数统计入答案即可.如果不在就将之前找到过的满足条件的与当前客栈颜色相同的客栈数统计入答案.

Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=200005;
int n,k,p,col[N],cost[N],last[N],cnt[N],lastp,ans,sum[N];
int main(){
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&col[i],&cost[i]);
    }
    for(int i=1;i<=n;i++){
        if(cost[i]<=p){
            lastp=i;
        }
        if(lastp>=last[col[i]]){
            sum[col[i]]=cnt[col[i]];
        }
        last[col[i]]=i;
        cnt[col[i]]++;
        ans+=sum[col[i]];
    }
    printf("%d\n",ans);
    return 0;
}