题解 P1311 【选择客栈】
介绍一下我的 O（n）做法 并且代码量全网最低！
不压行也只有19行！哪有其它大佬的题解那么麻烦
也没有很多奇奇怪怪的变量 自认为非常简洁
题解有得点长 但是很详细很好懂 dalao闲我啰嗦可以直接看代码
下面进入正题：
先解释题意 题意大家应该都很清楚了
简单来讲就是在一段一维客栈中 任意选择两个客栈a,b
客栈a,b满足两个条件
1. a,b颜色相同
2. [a,b]闭区间之间必须存在某个客栈的咖啡店的花费<=p;
我们要求成立的a,b共有多少对
既然是O（n）的做法 那我们肯定是枚举
因为我们要找到所有成立的 a,b
那么我们就枚举每个b 想办法找到此时符合条件的a有多少个
先解释下变量t
t记录的是当前枚举客栈过程中 离我们枚举到的客栈最近的
最低消费<=p的客栈的下标（第几个客栈）
例如 样例 p=3
我们枚举到1号客栈是 5>3 t=0;
枚举2号客栈 3<=3 发现成立 t=3;
枚举3号客栈 2<=3 t=2;
那么 t有什么用呢？
仔细一想我们会发现（敲黑板 重点！）
我们枚举b时 此时成立的a的个数
a要成立 显然a一定要在t前面
这样就满足了上述第二个条件
a要成立 是不是还要满足第一个条件？
第一个条件是什么 不是a,b颜色相同?
那此时a成立的个数 不就在t前面 和b颜色相同的客栈的个数？
那就开个数组（num[ ]）实时更新在t前面的各个颜色的客栈有多少个啊
快速模拟一下样例 我们枚举到2号客栈时 t更新为3 num[1]++（1号颜色的客栈数）;
枚举到三号客栈，t又更新为2 ，num[0]++，ans+=num[0],ans=1;
枚举到4号客栈 ans+=num[1],ans=2;
枚举到5号客栈 ans+=num[1],ans=3；
这时我们就得到了答案 当然我们还用了一个color数组记录每个客栈的颜色
再提几点注意的地方
- 我们每发现新的符合条件的t 都要把(pre,t]区间客栈对应的颜色++（实时更新）
（pre）是上一个t， 同时注意上诉区间是左开右闭，这些细节问题自己很好想
2 如果这个客栈更新了t，ans+=num[这个客栈的颜色]-1
如果这个客栈没有更新t，ans+=num[这个客栈的颜色]
这也是细节问题 为什么呢
因为当这个客栈更新t时 我们在把(pre,t]区间客栈对应的颜色++
此时 这个客栈的颜色数包含了自己 所以要减一
还有不清楚的地方 请借助代码理解
写题解不易 望各位给我点个赞
下面是AC代码
#include<cstdio>
using namespace std;
int n,k,p,t,ans,price,num[110],color[200100];
int main()
{
scanf("%d%d%d",&n,&k,&p); // n个客栈 k个色调 有p块钱
for(int i=1;i<=n;i++)
{
scanf("%d%d",&color[i],&price);
if(price<=p)
{
for(int j=i;j>t;j--) num[color[j]]++;
t=i,ans+=num[color[i]]-1;
}
else ans+=num[color[i]];
}
printf("%d",ans);
return 0;
}