题意描述

给定 $n$ 个数的数组 $a$，求一个子集，使和属于 $[L,R]$。

$\bm{R−L≥\max\{a\}−\min\{a\}},n\le2\times10^5,a_i,L,R<=2^{31}-1$。

题解

初见很像 0-1 背包，但显然数据范围并不适用。

我们发现 $R−L≥\max\{a\}−\min\{a\}$ 这个特殊性质很古怪，考虑它的意义。当加上集合中的一个元素再减去一个元素，变化量不会超过 $R-L$。我想到这里就不会了，实际上这需要一个神奇的构造：当序列排序后，答案是一个连续子段。

下证：存在一个大小为 $k$ 的子集，元素之和属于 $[L,R]$，当且仅当存在一个长度为 $k$ 的连续子段，元素之和属于 $[L,R]$。

充分性显然，连续子段也是子集。

必要性：设该大小为 $k$ 的子集元素和为 $x\in[L,R]$。 考虑所有长度为 $k$ 的连续子段和：

$$s_j=a_j+a_{j+1}+\cdots+a_{j+k-1},\quad j=1,2,\dots,n-k+1$$

由于数组单调不降，有

$$s_1\le s_2\le\cdots\le s_{n-k+1}$$

任意 $k$ 个元素之和的最小值是前 $k$ 个元素之和，最大值是后 $k$ 个元素之和，因此

$$s_1\le x\le s_{n-k+1}$$

反证法。假设所有 $s_j$ 都不在 $[L,R]$ 内，由于 $x\in[L,R]$，必存在相邻两项满足

$$s_t<L,s_{t+1}>R$$

从而

$$s_{t+1}-s_t>R-L$$

但这与

$$s_{t+1}-s_t\le a_{j+k}-a_j\le a_n-a_1\le R-L$$

矛盾。 因此假设不成立。 必有一个 $s_j\in[L,R]$。

双指针维护即可。每次右指针向右移动一格时，左指针一直右移直到总和 $\le R$。

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

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,l,r,b[200010];
ll L,R,a[200010],sum;
int main(){
	scanf("%d%lld%lld",&n,&L,&R);
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
		b[i]=i;
	}
	sort(b,b+n,[](ll x,ll y){
		return a[x]<a[y];
	});
	for(;r<n;r++){
		sum+=a[b[r]];
		for(;sum>R;l++) sum-=a[b[l]];
		if(sum>=L) break;
	}
	if(L<=sum&&sum<=R){
		printf("%d\n",r-l+1);
		for(int i=l;i<=r;i++){
			printf("%d ",b[i]);
		}
	}
	else printf("0");
}