TopCoder SRM680(Div.1) Easy BearFair

Posted on By 二价氢

题目大意

是否存在一个集合满足一下条件:

  1. 集合内的元素互不相等且均小于等于

  2. 集合里恰有个偶数与奇数

  3. 内恰有个数

其中有若干组

解法

对于第一个条件,我们可以将其与第三个条件合并,即在范围内恰有个数

于是我们维护以下三点:

  1. 内至多有MaxEven个偶数

  2. 内至多有MaxOdd个奇数

  3. 内至多有MaxNumber个数

于是,集合存在的充要条件是下面三点:

通过反证法可以知道其正确性,首先第三点的正确性是显然的,现在来说明第一点和第二点:

已知集合里有只多MaxEven个偶数,那么偶数的个数肯定可以是,因而,奇数的个数是,因而一定存在满足题意的集合。

于是我们统计出MaxEven、MaxOdd、MaxNumber即可,具体的计算方法见代码。

###Code

#define ut( _x ) vec[ _x ].first
#define qu( _x ) vec[ _x ].second
class BearFair {
public:
	string isFair(int n, int b, vector <int> upTo, vector <int> quantity) {
		int cnq = upTo.size();
		vector< pair<int, int> > vec;
		vec.push_back(make_pair(0, 0));
		for (int i = 0; i < cnq; i++)
			vec.push_back(make_pair(upTo[i], quantity[i]));
		vec.push_back(make_pair(b, n));
		sort(vec.begin(), vec.end());
		int mxe = 0, mxo = 0, mxc = 0;
		mxe = min(ut(0) / 2, qu(0));
		mxo = min((ut(0) + 1) / 2, qu(0));
		for (int i = 1; i <= cnq + 1; i++) {
			if (qu(i) < qu(i - 1))
                            return "unfair";
			if (ut(i) == ut(i - 1) && qu(i) != qu(i - 1))
                            return "unfair";
			if (ut(i) - ut(i - 1) < qu(i) - qu(i - 1))
                            return "unfair";
			mxe += min(ut(i) / 2 - ut(i - 1) / 2, qu(i) - qu(i - 1));
			mxo += min((ut(i) + 1) / 2 - (ut(i - 1) + 1) / 2, qu(i) - qu(i - 1));
		}
		return (mxe < n / 2 || mxo < n / 2) ? "unfair" : "fair";
	}
};

Level Upper 2016 - TopCoder 250 : 1 / 5