Subsequence

Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 30339
 
Accepted: 12756

Description

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

Sample Input

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

Sample Output

2
3

Source

Southeastern Europe 2006

제목의 대의.

N개의 양의 정수(10)를 포함하는 시퀀스를 지정합니다.

사고의 방향

첫 번째 방법은 O(n)로 접두사와 각 왼쪽 끝을 하나하나 열거한 다음lowerbound에서 첫 번째 오른쪽 단점을 찾습니다. 복잡도는 O(nlogn)이고 길이마다min을 찾으면 됩니다. (구체적으로 코드 참조)
두 번째 방법은 척취법으로 왼쪽 점 l과 오른쪽 점 r를 0으로 초기화한다

만약sum

이전 단계를 거쳤든 안 거쳤든 상관없이sum>=s만 있으면 길이는min

왼쪽 점 l++,sum에서 a[l]를 빼고 각 왼쪽 점을 매거하는 목적을 달성하고 앞 두 단계를 계속한다

왼쪽 끝과 오른쪽 끝은 항상 오른쪽으로 이동하고 시간 복잡도는 O(n)(코드 참조)
Tip:poj 데이터가 약해서 답이 1인 경우는 없는 것 같습니다. 첫 번째 방법 코드의 설명을 보십시오.

코드

접두사 및 열거 왼쪽 끝점 + 이분

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair PII;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
ll qpow(ll base, ll n){
	ll ans = 1;
	while (n){
		if (n & 1) ans = ans * base % mod;
		base = base * base % mod;
		n >>= 1;
	}
	return ans;
}
int sum[N];
int main()
{
	int t;
	cin >> t;
	while (t --){
		int n, s;
		cin >> n >> s;
		for (int i = 1; i <= n; ++ i) {
			scanf("%d", &sum[i]);
			sum[i] += sum[i - 1];
		}
		if (sum[n] < s) {
			printf("0
");
			continue;
		}
		int ans = INF;
		for (int l = 1; sum[n] - sum[l - 1] >= s; ++ l){
			int r = lower_bound(sum + l, sum + n + 1, sum[l - 1] + s) - sum;
			//       lower_bound(sum + l + 1, sum + n + 1, sum[l - 1] + s) - sum
			//        ，  a[i]       s   ,    1   
			ans = min(ans, r - l + 1);
		}
		printf("%d
", ans);
	}
	return 0;
}

척취법

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair PII;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
ll qpow(ll base, ll n){
	ll ans = 1;
	while (n){
		if (n & 1) ans = ans * base % mod;
		base = base * base % mod;
		n >>= 1;
	}
	return ans;
}
int a[N];
int main()
{
	int t;
	cin >> t;
	while (t --){
		int n, s;
		cin >> n >> s;
		for (int i = 1; i <= n; ++ i) {
			scanf("%d", &a[i]);
		}
		int sum = 0, l = 0, r = 0;
		int ans = INF;
		while (r <= n){
			while (r <= n && sum < s){
				sum += a[++ r];
			}
			if (sum < s) break;//  sum < s,         
			ans = min(ans, r - l);
			sum -= a[++ l];
		}
		if (ans == INF) ans = 0;
		printf("%d
", ans);
	}
	return 0;
}