UOJ235 【IOI2016】molecules 题解

题目链接：#235. 【IOI2016】molecules

题意：

cxy 在一家公司工作，这家公司已经制造了一台检测分子的机器。每个分子的重量都是正整数。这台机器的检测范围是 $[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$：分子的重量。

如果存在符合要求的子集，该函数应该返回一个数组，数组中的元素代表符合要求的子集中的分子的下标。如果存在多个正确答案，返回任何一个子集即可。

如果不存在符合要求的子集，该函数应该返回一个空数组。

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

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

评测方式：

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

第一行：整数 $n, l$ 和 $u$。

第二行：$n$ 个整数：$w_0, \ldots, w_{n - 1}$。

数据范围：

$n \le 2\times 10^5,~u,l,w_i \le 2^{31} -1$

一看这个选子集，还什么求和的，就想到这道题

~~又根据直觉~~，所以盲猜答案是排序后的一个子段，结果还真的是这样的。

考虑排序后使用尺取法。

尺取法其实就是维护两个指针，用 $O(n)$ 的时间计算出每个左端点 $l_i$ 的极大答案 $f(l_i,r_i)$

因为 $u - l \ge w_{\max} - w_{\min}$ ，所以左边去掉一个数，右边加入一个数

它的影响不会超过 $w_{\max}-w_{\min}$ ，也不会超过 $u-l$ ，故尺取法一定不会错过答案。

反之，如果没有这个保证，答案就不一定是一个连续区间了（因为可能中间选的实际上不要选，结果你尺取法选了，导致本应要选的选不了了），~~那样可不可做我就不知道了~~

时间复杂度 $O(n \log n)$ ，瓶颈在排序

代码：

#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
#define N (int)(2e5+15)
#define ll long long
typedef vector<int> vec;

int n,o[N]; ll s[N];
vec *_w;
bool cmp(int a,int b){return (*_w)[a] < (*_w)[b];}
#define a(x) (w[o[x]])
vec find_subset(int l,int u,vec w)
{
    n=w.size(); _w=&w; ll sum=0;
    for(int i=0; i<n; i++) o[i]=i;
    sort(o,o+n,cmp);
    for(int L=0,R=0; L<n; L++)
    {
        while(sum < l && R < n) sum += a(R++);
        if(l <= sum && sum <= u)
            return vec(o+L,o+R); // (vec){o[L], o[L+1], ... o[R-1]}
        sum -= a(L);
    }
    return vec();
}