• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Two Pointers Method Step3 I.Segment with the Required Subset 双指针 + 01布尔背包 + 两个栈维护

开发技术 开发技术 1周前 (05-01) 5次浏览

Two Pointers Method Step3 I.Segment with the Required Subset 双指针 + 01布尔背包 + 两个栈维护

题意

给定长度为(n)的数组(a),一个字段(a[l:r])被称为good当且仅当能够选出若干个数使得他们的和为(s),任务是找到最短的good段

[1 leq n leq 10^5\
1 leq s leq 10^3\
1leq a_i leq s\
]

分析

显然这样的性质具有单调性,也就是对于固定的(r),我们不需要重新枚举(l)

因此此题可以用双指针做,维护这个性质显然可以用01布尔背包,可以用bitset优化个常数。

具体怎么删除呢?这里用到技巧是开动态的两个栈来维护,对于加入的数先加入(st2),显然(st2)里的数的下标是逆序的,删除的时候,若(st1)中为空,就把这个时候(st2)的所有元素都加入到(st1)中,这个时候从栈顶开始就是正序的,因此直接pop栈顶元素即可。

判断good的时候只需要遍历两个栈中的元素然后判断能否拼出(s)即可

每个数最多进栈出栈两次,总复杂度(O(ns))

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),x.end()

using namespace std;
typedef long long ll;

ll rd(){
	ll x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x;
}

struct Stk{
	vector<int> stk;
	vector<bitset<1005>> bit;
	void init(){
		bitset<1005> tmp;
		tmp[0] = 1;
		bit.push_back(tmp);
	}
	void push(int x){
		stk.push_back(x);
		bitset<1005> tmp = bit.back();
		bit.push_back(tmp | (tmp << x));
	}
	int top(){
		return stk.back();
	}
	bitset<1005> get(){
		return bit.back();
	}
	void pop(){
		stk.pop_back();
		bit.pop_back();
	}
	bool empty(){
		return stk.empty();
	}
}s1,s2;

void add(int x){
	s2.push(x);
}

void del(){
	if(s1.empty()) {
		while(!s2.empty())
			s1.push(s2.top()),s2.pop();
	}
	s1.pop();
}

int s;
int n;

int a[100005];

bool good(){
	bitset<1005> v1 = s1.get();
	bitset<1005> v2 = s2.get();
	for(int i = 0;i <= s;i++){
		if(v1[i] && v2[s - i]) 
			return 1;
	}
	return 0;
}

int main(){
	s1.init();
	s2.init();
	n = rd();
	s = rd();
	for(int i = 1;i <= n;i++){
		a[i] = rd();
	}
	int l = 1;
	int ans = 1e9;
	for(int i = 1;i <= n;i++){
		add(a[i]);
		while(good()) {
			ans = min(ans,i - l + 1);
			del();
			l++;
		}
	}
	if(ans == 1e9) ans = -1;
	cout << ans << 'n';
}

喜欢 (0)