记录编号	34099	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]选择客栈	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.112 s
提交时间	2011-11-29 19:56:37	内存使用	1.84 MiB

#include<fstream>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");

int n,p,k;
class Info
{
public:
	int Color,Price;
}in[200001];

int f[51];
int pointer[51];
//pointer[i]:当前色调为i的旅店之前有多少
//满足题意个匹配
int before=1;
//before:目前最接近当前位置的满足
//要求的位置
int main()
{
int i,j;
	fin>>n>>k>>p;
	for(i=1;i<=n;i++)
		fin>>in[i].Color>>in[i].Price;
	int s=0;
	pointer[in[1].Color]=1;
	for(i=1;i<=n;i++)
	{
		if(before!=i){
			if(in[i].Price <= p)
			{
				for(j=before+1; j<=i ;j++)
					pointer[in[j].Color]++;
				before = i;
				s=pointer[in[i].Color]-1;
			}
			else
				s=pointer[in[i].Color];
		}
		f[in[i].Color]+=s;
	}
	int Sum=0;
	for(i=0;i<k;i++)
		Sum+=f[i];
	fout<<Sum<<endl;
	
	fin.close();
	fout.close();
	return 0;
}