这一道题,仔细想想就会发现可以用枚举暴......

先别骂!不是真·暴力,而是用O(n)的时间复杂度做出来的。

思路:

选择的俩客栈我们称为a和b。

我们把客栈b枚举一次,答案就是符合要求的客栈a的个数的和,对吧?

开一个变量t,t是枚举时可以去的咖啡馆。记录的是当前枚举客栈过程中,离我们枚举到的客栈最近的且最低消费<=p的客栈的下标。

我们枚举b时,此时a要成立的话,一定要在t前面(因为题目要求t一定要在a和b之间,而b已经在t之后了) ,还要!颜色一样。(什么奇葩的旅客啊...)

那此时a成立的个数,就是...和b颜色相同的客栈的个数!

那就开个数组num[]!实时更新在t前面的各个颜色的客栈有多少个(省时间啊),并实时更新。

代码还是比较简单和简短的、、

蒟蒻の代码:

//暴暴暴暴...力
#include <iostream>
using namespace std;

int t,cnt,num[101],color[200001];//cnt是答案数,color[]是输入的颜色,其它的如文字说明所述(懒.jpg

int main()
{
	int n,k,p;
	cin >> n >> k >> p;
	for(int i = 1;i <= n;i++)
	{
		int price;
		cin >> color[i] >> price;
		if(price <= p)//钱是可以的
		{
			for(int j = i;j > t;j--) num[color[j]]++;//前面这个颜色的个数加一
			t = i;//所以这个客栈也行,更新t
			cnt += num[color[i]] - 1;//cnt要加上前面相同颜色的个数
		}
		else cnt += num[color[i]];//看不懂见下↓
	}
	cout << cnt;
	return 0;
}

提醒:-

1. 刚刚代码里: 如果这个客栈更新了t,ans+=num[这个客栈的颜色]-1

   如果这个客栈没有更新t,ans+=num[这个客栈的颜色]

   What?Why?How?

   因为此时这个客栈的颜色数包含了自己所以要...

2. 没了

感慨:

真难啊!

—:感慨个透啊!讲完了就拜拜别浪费时间

我:哦