UOJ Logo Universal Online Judge

UOJ

#235. 【IOI2016】molecules

统计

彼得在一家公司工作,这家公司已经制造了一台检测分子的机器。每个分子的重量都是正整数。这台机器的检测范围是 $[l, u]$,这里 $l$ 和 $u$ 都是正整数。这台机器能够检测一个分子集合当且仅当这个集合包含了一个子集,这个子集的分子的重量属于机器的检测范围。

考虑 $n$ 个分子,重量记为 $w_0, \ldots, w_{n - 1}$。如果存在一个下标的集合(并且该集合中的下标都不相同)$I = \{i_1, \ldots, i_m\}$ 使得 $l \le w_{i_1} + \cdots + w_{i_m} \le u$,那么检测就会成功。

由于机器的细节,$l$ 和 $u$ 之间的差距要保证会大于等于最重分子和最轻分子之间的差距,即 $u - l \ge w_{\max} - w_{\min}$,其中 $w_{\max} = \max(w_0, \ldots, w_{n - 1})$,$w_{\min} = \min(w_0, \ldots, w_{n - 1})$。

你的任务是写一个程序,该程序能找到一个子集,使得该子集的总重量属于检测范围,或者判定没有这样的子集存在。

实现细节

你应该实现一个函数(方法):

  • std::vector<int> find_subset(int l, int u, std::vector<int> w)
    • $l$ 和 $u$:分别表示检测范围的两个端点,
    • $w$:分子的重量。
    • 如果存在符合要求的子集,该函数应该返回一个数组,数组中的元素代表符合要求的子集中的分子的下标。如果存在多个正确答案,返回任何一个子集即可。
    • 如果不存在符合要求的子集,该函数应该返回一个空数组。

你的程序可以将分子的下标以任何顺序写入返回的数组中。

请使用提供的模板文件,参考关于你所使用的编程语言的实现细节。

样例一

find_subset(15, 17, [6, 8, 8, 7])

这个例子当中,我们有四个分子,重量分别是 $6,8,8$ 和 $7$。这台机器可以检测子集总重量在 $15$ 到 $17$ 之间(包含 $15$ 和 $17$)的子集。注意,$17 - 15 \ge 8 - 6$。分子 1 和分子 3 的重量之和为 $w_1 + w_3 = 8 + 7 = 15$, 所以这个函数应该返回 $[1, 3]$。其他可能正确的答案有 $[1, 2]$($w_1 + w_2 = 8 + 8 = 16$)和 $[2, 3]$($w_2 + w_3 = 8 + 7 = 15$)。

样例二

find_subset(14, 15, [5, 5, 6, 6])

这个例子当中,我们有四个分子,重量分别为 $5,5,6$ 和 $6$,我们要寻找一个子集,其总重量介于 $14$ 和 $15$ 之间(包含 $14$ 和 $15$)。请注意,$15 - 14 \ge 6 - 5$。因为不存在总重量介于 $14$ 和 $15$ 之间的子集,所以该函数返回空数组。

样例三

find_subset(10, 20, [15, 17, 16, 18])

这个例子当中,我们有四个分子,重量分别为 $15,17,16$ 和 $18$,而且我们要寻找一个子集,其总重量介于 $10$ 和 $20$ 之间(包含 $10$ 和 $20$)。请注意,$20 - 10 \ge 18 - 15$。任何只包含一个元素的子集,其重量都在 $10$ 和 $20$ 之间,所以可能正确的答案有 $[0], [1], [2]$ 和 $[3]$。

子任务

子任务 分数 $n \le $ $w_i \le $ $u, l \le $ 其他约定
19$100$$100$$1000$所有 $w_i$ 都相等
210$100$$1000$$1000$$\max(w_0, \ldots, w_{n - 1}) - \min(w_0, \ldots, w_{n - 1}) = 1$
312$100$$1000$$1000$
415$10000$$10000$$10000$
523$10000$$500000$$500000$
631$200000$$2^{31} - 1$$2^{31} - 1$

评测方式

评测程序将会按照下列格式读取输入数据:

  • 第一行:整数 $n, l$ 和 $u$。
  • 第二行:$n$ 个整数:$w_0, \ldots, w_{n - 1}$。

交互式类型的题目怎么本地测试

时间限制:$1\texttt{s}$

空间限制:$2\texttt{GB}$

下载

样例及测评库下载