TopCoder SRM681(Div.1) Easy FleetFunding

Posted on By 二价氢

题目大意

一艘飞船需要个零件,有不超过50个工厂,第i工厂可以制造号到第号零件,同时第个工厂至多制造个零件,问最多能制造多少个零件?

解法

对于这种问题,最开始的做法肯定是先二分答案(我不会写二分所以用了倍增囧……)

对于答案的可行性,我们可以考虑使用贪心的方法解决,即从1号零件开始,尽量使用较小的工厂的额度(可以证明这样答案不会减小),然后扫一遍,看能否达到目的。

后面有另外一种思路,然而无法通过某些数据,我想知道为什么是错误的,希望有人能够指出,谢谢。

Code

typedef pair<pair<int, int>, int> pii;
#define x first
#define y second
class FleetFunding {
public:
	bool check(int k, const int m, vector<pii> v) {
		vector<int> vl(m + 1, k);
		for (int i = 1; i <= m; i++) {
			for (auto n = v.begin(); n != v.end(); n++) {
				if (n->x.x >= i && n->x.y <= i) {
					int add = min(n->y, vl[i]);
					vl[i] -= add;
					n->y -= add;
				}
			}
		}
		for (int i = 1; i <= m; i++) if (vl[i]) return false;
		return true;
	}
	int maxShips(int m, vector<int> k, vector<int> a, vector<int> b) {
		vector<pii> v;
		int n = k.size();
		for (int i = 0; i < n; i++)
			v.push_back(make_pair(make_pair(b[i], a[i]), k[i]));
		sort(v.begin(), v.end());
		int ans = 0;
		for (int i = (1 << 30); i; i >>= 1)
			if (check(ans | i, m, v))
				ans |= i;
		return ans;
	}
};

错误的做法

考虑题设,可以认为题目里的条件是能在之间提供的额度,而超出这个区间,额度就会作废。

因而,我们可以在进入某个区间的时候,给可用额度加上某个值,在退出区间的时候,看看额度用了多少,将没有使用的额度作废,任何时候,如果可用额度小于0,则返回否。

然而,这种看似毫无问题的做法……是错误的,然而,其对于大多数随机的情况,都不会出现问题。

如何Cha掉这个做法:

参数

显然,正确答案是1,然而这个做法会得出2,究其原因,就是这个做法实际上抛弃了额度的有效范围,而简单地加上额度或减少额度,对于这个Case,,然而其只能在2号位使用,而当我们二分到2这个答案的时候,将这个区间的额度提前用完,而在2号位又用了2没有用完的额度,自然就WA了。

如何解决这个问题,也很简单,就是我们要分别存储额度的有效范围,然后分不用的范围减少额度,我们发现,这样就是前面的正确做法了。

至于为什么这个做法是错误的,也很简单,这个问题当且仅当某个大区间完全包含了某个小区间,且小区间的额度能满足整个大区间的需要时才会出现。对于大部分随机数据,都很难出现这样的情况。

另外,我似乎要改一下意识流的变量命名规则了囧……

Code2

#define x first
#define y second
class FleetFunding {
public:
	bool check(int k, const int m, const vector<pii> &v1, const vector<pii> &v2) {
		long long used = 0, left = 0;
		int ptr1 = -1, ptr2 = -1;
		for (int i = 1; i <= m; i++) {
			while (v1[ptr1 + 1].x <= i) {
				ptr1++;
				left += v1[ptr1].y;
			}
			left -= k;
			used += k;
			while (v2[ptr2 + 1].x <= i) {
				ptr2++;
				int add = min(v2[ptr2].y, giv);
				used -= add;
				left -= v2[ptr2].y - add;
			}
			if (left < 0) return false;
		}
		return true;
	}
	int maxShips(int m, vector<int> k, vector<int> a, vector<int> b) {
		vector<pii> v1, v2;
		int n = k.size();
		for (int i = 0; i < n; i++)
			v1.push_back(make_pair(a[i], k[i])),
			v2.push_back(make_pair(b[i], k[i]));
		v1.push_back(make_pair(m + 2, 0));
		v2.push_back(make_pair(m + 2, 0));
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());
		int ans = 0;
		for (int i = (1 << 24); i; i >>= 1)
			if (check(ans | i, m, v1, v2))
				ans |= i;
		return ans;
	}
};

Level Upper 2016 - TopCoder 250 : 3 / 5