题目大意
是否存在一个集合满足一下条件：
-
集合内的元素互不相等且均小于等于\(b\)
-
集合里恰有\(\frac{n}{2}\)个偶数与\(\frac{n}{2}\)奇数
-
在\([1, \mathrm{upTo}_i]\)内恰有\(\mathrm{quantity}_i\)个数
其中\(\mathrm{upTo}_i\)与\(\mathrm{quantity}_i\)有若干组
解法
对于第一个条件，我们可以将其与第三个条件合并，即在\([1, b]\)范围内恰有\(n\)个数
于是我们维护以下三点：
-
在\([1, \mathrm{upTo}_i]\)内至多有MaxEven个偶数
-
在\([1, \mathrm{upTo}_i]\)内至多有MaxOdd个奇数
-
在\([1, \mathrm{upTo}_i]\)内至多有MaxNumber个数
于是，集合存在的充要条件是下面三点：
- \[\mathrm{MaxEven}\ge \frac{n}{2}\]
- \[\mathrm{MaxOdd}\ge \frac{n}{2}\]
- \[\mathrm{MaxNumber}=n\]
通过反证法可以知道其正确性，首先第三点的正确性是显然的，现在来说明第一点和第二点：
已知集合里有只多MaxEven个偶数，那么偶数的个数肯定可以是\(\frac{n}{2}\)，因而，奇数的个数是\(\mathrm{MaxNumber}-\frac{n}{2}=\frac{n}{2}\le\mathrm{MaxOdd}\)，因而一定存在满足题意的集合。
于是我们统计出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