<commit_before>---
layout: post
title: TopCoder SRM681(Div.1) Easy FleetFunding
tags: [TopCoder, 贪心, 二分]
category: TopCoder
---
### 题目大意

一艘飞船需要$$m$$个零件，有不超过50个工厂，第i工厂可以制造$$a_i$$号到第$$b_i$$号零件，同时第$$i$$个工厂至多制造$$k_i$$个零件，问最多能制造多少个零件？

### 解法

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

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

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

### Code

```cpp
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;
	}
};
```

### 可能错误的做法

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

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

### Code2

```cpp
#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 giv = 0, lst = 0;
		int ptr1 = -1, ptr2 = -1;
		for (int i = 1; i <= m; i++) {
			while (v1[ptr1 + 1].x <= i) {
				ptr1++;
				lst += v1[ptr1].y;
			}
			lst -= k;
			giv += k;
			if (lst < 0) return false;
			while (v2[ptr2 + 1].x <= i) {
				ptr2++;
				int add = min(v2[ptr2].y, giv);
				giv -= add;
				lst -= v2[ptr2].y - add;
			}
			if (lst < 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])),<commit_msg>Edit a Wrong Solution<commit_after>---
layout: post
title: TopCoder SRM681(Div.1) Easy FleetFunding
tags: [TopCoder, 贪心, 二分]
category: TopCoder
---
### 题目大意

一艘飞船需要$$m$$个零件，有不超过50个工厂，第i工厂可以制造$$a_i$$号到第$$b_i$$号零件，同时第$$i$$个工厂至多制造$$k_i$$个零件，问最多能制造多少个零件？

### 解法

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

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

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

### Code

```cpp
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;
	}
};
```

### 错误的做法

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

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

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

如何Cha掉这个做法：

| 参数 | 值 |
|:-:|:-:|
| $$n$$ | $$3$$ |
| $$k$$ | $$\{2, 4\}$$ |
| $$a$$ | $$\{1, 2\}$$ |
| $$b$$ | $$\{3, 2\}$$ |

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

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

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

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

### Code2

```cpp
#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])),
{'fraction_non_alphanumeric': 0.21036073825503357, 'fraction_numerical': 0.02307046979865772, 'mean_word_length': 3.5944123314065513, 'pattern_counts': {'":': 0, '<': 54, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7136703', 'n_tokens_mistral': 3043, 'n_tokens_neox': 3006, 'n_words': 498}