题解 CF1106B 【Lunar New Year and Food Ordering】

Anguei

2019-02-01 02:21:03

Solution

模拟题。题面较长,在打 CF 的时候需要耐心读完题目(这也就是比赛时 C 已有 200 AC 时此题 AC 数为零的原因)。 题目要求先考虑最便宜的饭菜,当价格相同的时候考虑序号小的。然而我排序的时候漏掉了第二个条件竟然没有 FST,可能是数据水吧。 有人使用 `for (int i = 1; i <= m; ++i)` 在其中有些了 `i` 的循环,导致样例全过却奇妙的 Wa on #7。所以还是 `while (m--)` 比较安全。 使用 `map` 保存可以简化一下代码。当然这不是必须的。 剩下的就是根据题目指出的三种情况进行模拟了,不难。 ```cpp const int N = 100000 + 5; struct Data { int id, a, c; Data(){} Data(int id, int a, int c) : id(id), a(a), c(c) {} bool operator<(const Data &rhs) const { return c < rhs.c; // 这里严格来讲应该加一个比较条件 } } x[N]; int n, m, pos = 1; std::map<int, int> map; void solution() { n = read(), m = read(); rep(i, 1, n) x[i].a = read(), x[i].id = i; rep(i, 1, n) x[i].c = read(); std::sort(x + 1, x + n + 1); rep(i, 1, n) map[x[i].id] = i; while (m--) { int t = read(), d = read(), ans = 0; t = map[t]; // 下面是分三种情况进行模拟。 if (x[t].a >= d) ans = d * x[t].c, x[t].a -= d, d = 0; else { ans = x[t].a * x[t].c, d -= x[t].a, x[t].a = 0; while (pos <= n && d) { int now = std::min(d, x[pos].a); d -= now, x[pos].a -= now; ans += now * x[pos].c; if (!x[pos].a) ++pos; } } println(d ? 0 : ans); } } ```