用时：20 min 时间复杂度：O(kn)
还算是比较简单的一道题，先看部分分，发现暴力可以拿50。暴力的做法是枚举每个合法咖啡店左右两端相同颜色的客栈。
考虑优化，由于本题中每个合法点都对答案造成影响，很容易想到维护某种前缀和。
而从输入过程中每个点的影响，无论该点是否合法，该点上的客栈都对答案做出贡献（可为 0 ），需要知道的是离该点最近的合法点的位置前与该点颜色相同的点数
那么维护这两个值就可以了，详细见代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 200100
using namespace std;
int n,k,p;
int col[maxn][60],hf[maxn];
int read()
{
int ans=0,op=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)op=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){ans=ans*10+ch-‘0‘;ch=getchar();}
return ans*op;
}
int main()
{
n=read();k=read();p=read();
int ans=0;
for(int i=1;i<=n;i++)
{
int color=read();int price=read();
for(int j=0;j<k;j++)
col[i][j]=col[i-1][j];
col[i][color]++;
if(price<=p) hf[i]=i,ans--;
else hf[i]=hf[i-1];
ans+=col[hf[i]][color];
}
printf("%d\n",ans);
return 0;
}
原文：https://www.cnblogs.com/charlesss/p/10946682.html