洛谷 P1311 选择客栈

题目传送门

从左到右扫描区间,每往右一格,就找当前最靠右且最低消费满足题意的点k,对于当前点i,点k及其之前的所有与i相同颜色的点都可以与i匹配,答案加k前及k与i颜色相同的点的数量.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>

using namespace std;

int n,k,p,a[200001],num[51],b[200001];
int sum[51][200001],R,ans;

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 j = 0;j < k; j++) {
			if(a[i] == j) sum[j][i] = sum[j][i-1] + 1;
			else sum[j][i] = sum[j][i-1];
		}
	}
	for(int i = 1;i <= n; i++) {
		if(b[i] <= p) R = i;
		if(R != 0 && R == i) ans += sum[a[i]][R-1];
		if(R != 0 && R != i) ans += sum[a[i]][R];
	}
	printf("%d",ans);
	return 0;
}