题目大意
一艘飞船需要\(m\)个零件，有不超过50个工厂，第i工厂可以制造\(a_i\)号到第\(b_i\)号零件，同时第\(i\)个工厂至多制造\(k_i\)个零件，问最多能制造多少个零件？
解法
对于这种问题，最开始的做法肯定是先二分答案（我不会写二分所以用了倍增囧……）
对于答案的可行性，我们可以考虑使用贪心的方法解决，即从1号零件开始，尽量使用\(b_i\)较小的工厂的额度（可以证明这样答案不会减小），然后扫一遍，看能否达到目的。
后面有另外一种思路，然而无法通过某些数据，我想知道为什么是错误的，希望有人能够指出，谢谢。
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;
}
};
错误的做法
考虑题设，可以认为题目里的条件是能在\([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
#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