AcWing 500. 选择客栈
原题链接
中等
作者:
不幸到吃土
,
2025-01-08 23:39:24
,
所有人可见
,
阅读 3
/*
以如下为例,其中第3号客栈为"已有遍历中满足低消条件"的客栈
编号:1 2 3 4 5 6(新加)
客栈:白 白 白 黑 白 白
对于新遍历到的第6号客栈,有两种情况:(1)满足低消 (2)不满足低消
(1)若满足低消
此时6号客栈可作为选择,有4种新的方案:1-6、2-6、3-6、5-6 (以6号为主选择,其余颜色相同的客栈均可作为另一个选择)
(2)若不满足低消
此时仍以3号客栈作为选择,有3种新的方案:1-6、2-6、3-6 (仍以3号为主选择,新的6号客栈仅作为另一个选择)
---------------------------------------------------------
基于上述分析,设(j,i)为当前遍历客栈的区间,另设last指向最近满足低消的客栈,并对a[i]进行判断
若符合(1),则另j指向last,开始遍历(j,i)
若符合(2),则last无需更改
*/
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 200010 , k = 55;
int c[N]; //c[]记录颜色
LL h[k]; //h[]记录各颜色对应客栈的数量
int main(){
int n,k,p;
cin >> n >> k >> p;
LL ans = 0;
int last = 0;
for(int i=1,j=0;i<=n;i++){
int price;
cin >> c[i] >> price;
if(price <= p){
j = last+1;
while(j <= i) //若当前客栈满足低消,则(last,i)区间的客栈可作为新的选择方案,此时再++
h[c[j++]]++;
last = i; //更新last为当前客栈
ans += h[c[i]] - 1;
}else{ //若不满足低消,则方案数加上"最近低消的客栈之前已有的客栈 ~ 当前客栈"
ans += h[c[i]];
}
}
cout << ans << endl;
return 0;
}
关于调试出问题修改半小时都毫无进展于是一气之下点了提交答案发现AC这件事