[C++知识库]c++ 选择客栈

?

分析：

首先这个客栈的总数n最大值为20万用朴素做法的两重循环肯定会超时，所以要改变循环方式。

在输入的同时进行操作，当输入的旅店的最低消费小于等于p时进行更新，从后往前循环到上一个最低消费小于p的点（m），对每个遍历到的旅店相应的颜色+1（num[kz[j].sd]++，num[]为储存对应下标颜色的旅馆个数），然后更新ans（ans+=num[kz[i].sd]-1）因为kz[i]本身就是一个符合条件的旅店可以与前面的任意一个相同颜色的旅店组合成一个不重不漏地（因为是随输入更新，线性）新组合，更新m=i，然后当a！=0（即已更新了至少一个符合条件（最低消费<p）的旅店）且不符合最低消费<p时，对每个输入的点更新（ans+=num[kz[i].sd]）也就是这个num[kz[i].sd]所存储的旅馆与本旅馆间必定有一个符合条件的旅馆，最后直接输出ans即可（需要注意m的初值需设为-1，这样第一次遍历的时候可以遍历到0点；或者把i的初值设为1，m设为0也可）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=200010;
int n,k,p,ans;
int m=-1,a;//m初始化为1 
struct kezhan{
	int sd,xf;
}kz[N];
int num[51];
int main(){
	cin>>n>>k>>p;
	for(int i=0;i<n;i++){
		cin>>kz[i].sd;//旅馆的色调 
		cin>>kz[i].xf;
		if(kz[i].xf<=p){
			a++;//记录符合条件的点 
			for(int j=i;j>m;j--){
				num[kz[j].sd]++;//向前遍历到上一个符合条件的点或-1 
			}
			if(a>=1) ans+=num[kz[i].sd]-1;//更新 
			m=i;
		}
		else {
			if(a>0) ans+=num[kz[i].sd];//更新 
		}
	}
	cout<<ans;
	return 0;
}

?