ZROI P1376 题解

题面

点击此处展开题面

原始人

小 Z 作为一个考古发掘小组的成员，到河姆渡进行考古发掘。

河姆渡曾经有一片人迹罕至的森林，他在考古发掘之余发现这里生活着一种原始人。他们用三种贝壳进行商品交易。

一个原始人手上一共有 $s$ 个第一类贝壳。每一天，他都可以用他拥有的第一类贝壳，兑换另外两种贝壳进行商品交易（每一天的汇率都不一样）。

交易市场共开放 $n$ 天，共 $m$ 件商品，每件商品都只能用特定的贝壳来交换。现在他想从这些商品中换到任意的 $k$ 件商品。小Z想要你帮他用最短的时间用他所拥有的第一类贝壳换取 $k$ 件商品，但他专心于考古，于是让你帮忙算出结果。

输入格式

输入共 $m + 3$ 行。

第一行四个整数 $n, m, k, s$，具体意义详见题目描述。

第二行 $n$ 个整数 $a_j$，第 $i$ 个表示第 $i$ 天换取 1 个第二类贝壳需要几个第一类贝壳。

第三行 $n$ 个整数 $b$，第 $i$ 个表示第 $i$ 天换取 1 个第三类贝壳需要几个第一类贝壳。

接下来的 $m$ 行，每行两个整数 $t, c$，$t = 1, 2$ 分别表示必须要用第二类或第三类贝壳结账，$c$ 表示需要多少个该类贝壳。

输出格式

输出 1 行，一个整数，表示最少需要的天数；如果无解，输出 -1。

数据范围

• Subtask 1 (30pts): $n, m \leq 2000$。
• Subtask 2 (30pts)：只使用第二类贝壳。
• Subtask 3 (40pts)：无特殊限制。

对于 100% 的数据：

• $1 \leq n \leq 2 \times 10^5$
• $1 \leq k \leq m \leq 2×10^5$
• $1 \leq s \leq 10^9$
• $1 < a_j, b_i \leq 10^6$
• $t \in \{1, 2\}$
• $1 \leq c \leq 10^6$

解题

一看又是商品，马上准备写背包。

再一看。。

背包题是这样的？？背包显然不是正解。

分析可以发现，多留一天，可选的汇率就多一种。为了能买到足够的商品，所以我们要尽量选择汇率更小的那天兑换，意味着等量的第一种贝壳可换得更多的其他贝壳。

这样的话，对于第 $i$ 天，如果

$$a_i > \max_{j < i} a_j$$

那么我们就可以考虑选择第 $i$ 天，否则就考虑选择

$$\argmax_{j < i} a_j$$

这一天。

说人话

只考虑 1 ~ $i$ 期间汇率最小的那天。

证明：如果汇率不是最小，则换得的贝壳更少。由于商品价格一定，所以买到的商品数不会更多，即方案不会更优。

这样，每一天被考虑汇率组成序列 $d$，我们有 $d_i = \max \{d_{i - 1}, a_i\}$，对于 $b$ 同理。

容易发现 $d$ 具有单调不下降的性质，并且由于可行域是一个前缀，这道题应该使用——二分。

我们把每一天的序号（从 1 到 $n$）定义为这天的日期，二分买够 $k$ 个商品的日期即可。

对于商品，由于只要求足够的数量，所以优先考虑价格更低的商品。

因此，对商品按价格升序排序，选择的又是一个前缀。

那么对于以上的情况，解应该满足什么条件呢？

设：

	最小汇率的日期	买的数量	价格的前缀和
第二种贝壳	$e'$	$r'$	$p'$
第三种贝壳	$e''$	$r''$	$p''$

有：

$$\begin{cases} e' \times p'_{r'} + e'' \times p''_{r''} \leq s \\ r' + r'' \geq k \end{cases}$$

二分求解即可。

代码

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 2e5 + 5;
int a[N], b[N], t[N], c[N], n, m, k, s;
LL f[N];  // 不开 long long 见祖宗！

bool check(int mid) {
  LL t1 = INT64_MAX, t2 = INT64_MAX;  // 最小汇率
  for (int i = 1; i <= mid; ++i) {
    t1 = min(t1, LL(a[i]));
    t2 = min(t2, LL(b[i]));
  }
  for (int i = 1; i <= m; ++i) {  // 处理每个商品
    switch (t[i]) {               // 都按最小汇率兑换
      case 1: f[i] = t1 * c[i]; break;
      case 2: f[i] = t2 * c[i]; break;
    }
  }
  sort(f + 1, f + m + 1);
  LL ans = 0;
  for (int i = 1; i <= k; ++i) ans += f[i];  // 买了最便宜的 `k` 个
  return (ans <= s);                         // 是否能买够
}

int main() {
  scanf("%d%d%d%d", &n, &m, &k, &s);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
  for (int i = 1; i <= m; ++i) scanf("%d%d", &t[i], &c[i]);
  int l = 1, r = n, mid;
  while (l <= r) {
    mid = l + r >> 1;
    if (check(mid))
      r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d", (l <= n) ? l : -1);  // 越界则为无解
  return 0;
}