using namespace std;
int main()
{
int a=0,b=0,d=0,e=0,p=0,sum=0;
cin>>a>>b>>p;
int x[a][2];
for(d=0;d<a;d++)
{
cin>>x[d][0]>>x[d][1];
}
for(d=0;d<a;d++)
{
for(e=d+1;e<a;e++)
{
if(x[d][0]==x[e][0])
{
if((x[d][1]<=p)||(x[e][1]<=p))
{
sum=sum+1;
}
}
}
}
cout<<sum;
return 0;
}
思路1：（不想看可跳过）
假设sum[i]代表从第0个到第-1i个一共有多少个最低消费<=p的酒店
每次假设两个客栈(i和j)颜色相同，计算sum[j]-sum[i]就能算出中间有几个位置用来小聚
时间复杂度 O(N*N)
空间复杂度 O(N)
得分 50
思路2：思路1的优化（不想看可跳过）
我们知道有K种色调，每一种色调挂一个链表
if 不懂什么叫链表
{
写思路1去。。。这题别想着AC了。。。
return 0;
}
每一个链表维护一个值，表示当前从这种颜色的第0,1,2,....t(当前已经有t个这种颜色的客栈了)个到第t+1个中可满足条件的酒店个数，设为x[i](i是颜色)
当每次见到一个颜色为i的，先把答案加上x[i]，再进行以下2种操作之一
x[i] = x[i] (c[t+1]-c[t] = 0)
x[i] = t+1 (c[t+1]-c[t] > 0)
最后求出总方案数即可
求给分~
代码：（不想看可跳过）（写的很渣）
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<memory>
#include<string>
#include<math.h>
#include<time.h>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
vector<int> a[200005];
int b[200005];
vector<int>::iterator pl;
vector<int>::iterator pr;
long long sum=0;
int main()
{
int i;
int n,k,p,x,m;
scanf("%d%d%d",&n,&k,&p);
b[0]=0;
for (i=1;i<=n;i++)
{
scanf("%d%d",&x,&m);
a[x].push_back(i);
if (m<=p) b[i]=b[i-1]+1; else b[i]=b[i-1];
}
int kk;
for (i=0;i<k;i++)
{
kk=0;
if (a[i].begin()==a[i].end()) continue;
pr=a[i].begin();
pr++;
for (pl=a[i].begin();pr!=a[i].end();pl++)
{
if (pl==pr) {pr++;sum+=kk;}
if (pr==a[i].end()) break;
for (;(pr!=a[i].end())&&(b[*pr]==b[*pl-1]);pr++) sum+=kk;
if (pr==a[i].end()) break;
kk++;
}
}
printf("%d",sum);
return 0;
}