自动搬运

查看原文

来自洛谷，原作者为

	gznpp 星星夜月引路 爱带我回家

搬运于2025-08-24 22:18:08，当前版本为作者最后更新于2020-12-02 15:42:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：给定 $N$ 个数的集合 $A$，求出一个子集满足它的和在 $[L, R]$ 内。

特殊性质：$R - L \ge \max A - \min A$。

暴力：当然可以用 bitset 优化背包做，时间复杂度 $O(\dfrac{NW}{64})$，貌似可以过 Subtask 5。

这完全没有考虑特殊性质，而这正是正解不同之处。我们来探究一下它到底表达了什么。

正解：猜想对序列排序之后，答案可以是一个线段。

因为只要丢掉一个线段左侧的元素再增加一个右侧的元素，对答案的影响一定不超过 $\max A - \min A$，也就不超过 $R - L$，一定不会错过答案。

实现时先一路取前缀到和 $\le L$，然后模拟前面过程即可。复杂度瓶颈是排序的 $O(N \log N)$，双指针 $O(N)$。

Code:

#include <bits/stdc++.h>
#include "molecules.h"
#define rgi register int
#define ll long long
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
using namespace std;
int n;
ll s,L,R;
vector<int> ans;
vector<pii> a;
vector<int> find_subset(int LL,int RR,vector<int> w)
{
	n=w.size();
	L=LL,R=RR;
	for(rgi i=0;i<n;++i)
		a.push_back(mkp(w[i],i));
	sort(a.begin(),a.end());
	for(rgi l=0,r=0;l<n;++l)
	{
		while(s<L&&r<n)
			s+=(ll)a[r++].fi;
		if(s>=L&&s<=R)
		{
			for(rgi i=l;i<r;++i)
				ans.push_back(a[i].se);
			return ans;
		}
		s-=a[l].fi;
	}
	return vector<int>();
}

官方题解还有一种做法，就是答案可以是一段前缀加一段后缀。

其实道理是一样的，先把前缀取完然后慢慢减前缀长度加后缀后缀长度即可，每次移动也不会超过 $\max A - \min A \le R - L$，不会错过答案。

Code:

#include <bits/stdc++.h>
#include "molecules.h"
#define rgi register int
#define ll long long
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
using namespace std;
int n;
ll s,L,R;
vector<int> ans;
vector<pii> a;

vector<int> find_subset(int LL,int RR,vector<int> w) {
    n = w.size(); a.resize(n);
    L = LL, R = RR;
    for (int i = 0; i < n; ++i) {
        a[i].fi = w[i];
        a[i].se = i;
        s += (ll)w[i];
    }
    sort(a.begin(), a.end());
    for (int i = n - 1, j = n; i < j && i >= -1;) { // interval [0, i] \cup [j, n - 1]
        while (s > R && i >= 0) {
            s -= (ll)a[i].fi;
            --i;
        }
        if (L <= s && s <= R) {
            for (int k = 0; k <= i; ++k) ans.push_back(a[k].se);
            for (int k = j; k < n; ++k) ans.push_back(a[k].se);
            return ans;
        }
        --j;
        s += (ll)a[j].fi;
    }
    return vector<int>();
}