noip2011选择旅馆

1.审题：第一个人与第二个人入住的旅馆要求是同色的；

             两个人去消费的旅馆并没有要求与入住的旅馆是同色的（这点要小心）

2.要求记录以下数据：

1）a[color]表示当前同为颜色color的旅馆数

2）b[color]表示可以入住的颜色color的旅馆数

3.在线处理

1）当前price<=p，则更新b[color]，更新ans += b[] - 1 （减1的原因是当前旅馆是第二个人住的，ans是累加第一个人住的旅馆数

2）更新ans，因为没有更新b[color]，所以ans += b[]

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 55;
int n, k, p;
int ai, bi;
int a[N], b[N], ans; 
//a[ N ]: N号颜色到当前位置时的旅馆数
//b[ N ]：N号颜色可以入住的旅馆数 
int main(){freopen("P1311_1.in", "r", stdin);cin >> n >> k >> p;for(int i = 1; i <= n; i ++){cin >> ai >> bi;a[ai] ++;if(bi <= p){for(int j = 0; j <= k; j ++)//并不要求消费的旅馆与入住的旅馆同色 b[j] = a[j];ans += b[ai] - 1;//（第二人住当前旅馆。累加的是第一个人住的旅馆数，所以减1）}else ans += b[ai];	}cout << ans;return 0;
}