CodeFroces 831C. Jury Marks(STL的应用)

http://codeforces.com/problemset/problem/831/C

题目大意：有k个评委，n条pol记得的分数。评委从前往后依次评分。pol记得一些评委评完分的分数，这些分数不一定是按照时间给出的。问参赛者初试分数有多少种可能。

解法：我们想一种检验方式，要保证pol记得的分数全都满足。一开始我很笨的用了k²n的算法，一直tle。正解为，随便选一个分数，然后将他枚举k个位置，每次枚举他会得出其他分数，check一下pol记得的分数是否都存在于这些分数之中。如果都存在，则返回该种情况的初始分数。最后输出不同的初试分数有多少种。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
const int maxm = maxn * maxn * 4;
int k, n;
int a[maxn], b[maxn], c[maxn] = {0}, tmp;
multiset <int>::iterator iter;
bool Check(int s, int x) {
	multiset <int> ms;
	int ts = s;
	for(int i = x + 1; i <= k; i++) {
		s += a[i];
		ms.insert(s);
	}
	s = ts;
	for(int i = x; i > 0; i--) {
		ms.insert(s);
		s -= a[i];
	}
	tmp = s;
	int key = 0;
	for(iter = ms.begin(); iter != ms.end(); iter++) {
//		cout << *iter << " ";
		if(*iter == b[key])
			key++;
		if(key >= n)
			break;
	}
//	cout << endl;
	if(key >= n)
		return 1;
	return 0;
}

int main() {
	set <int> myset;
	scanf("%d%d", &k, &n);
	for(int i = 1; i <= k; i++) {
		scanf("%d", &a[i]);
	}
	for(int i = 0; i < n; i++) {
		scanf("%d", &b[i]);
	}
	sort(b, b + n);
	int ans = 0;
	for(int i = 1; i <= k; i++) {
//		cout << "case " << i << ": ";
		if(Check(b[0], i)) {
			myset.insert(tmp);
		}
	}
	
	cout << myset.size() << endl;
	return 0;
}