POJ 3061 Subsequence 题解法一：二分 + 遍历法二：双指针

末蓝、 2022-09-02 05:14 15阅读 0赞

# 题目链接 #

> https://vjudge.net/problem/POJ-3061

# 一、二分+遍历 #

利用二分的思想来解决，复杂度O(n \* log(n))  
首先预处理一个SUM\[n\]的递增数组，  
每次对于这个数组二分搜索差值不少于S的下一个索引值，  
直到数组的结尾。

每次二分搜索维护最小的索引差值，输出这个最小索引差值作为结果。

#### 注意，一定要处理不能成功找到符合条件的结果的情况，这种情况下输出结果为0。 ####

## 代码 ##

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int N, S;
    const int MAX_N = 100000;
    int A[MAX_N];
    int sum[MAX_N];
    
    void solve()
    {
        
    	sum[0] = A[0];
    	for (int i = 1; i < N; ++i)
    	{
        
    		sum[i] = sum[i - 1] + A[i];
    	}
    	int res = N + 1;
    	for (int i = 0; sum[i] + S <= sum[N - 1]; ++i)
    	{
        
    		int t = lower_bound(sum + i, sum + N - 1, sum[i] + S) - sum;
    		res = min(res, t - i);
    		//cout << "res:" << res << endl;
    	}
    	// 一开始忘记判断这个了，疯狂wa，找不到问题
    	if (res == N + 1)
    		res = 0;
    	cout << res << endl;
    }
    
    int main()
    {
        
    	int T;
    	cin.tie(0);
    	cout.tie(0);
    	cout.sync_with_stdio(false);
    	
    	cin >> T;
    	
    	while (T--)
    	{
        
    		cin >> N;
    		cin >> S;
    		for (int i = 0 ; i < N; ++i)
    		{
        
    			cin >> A[i];
    		}
    		
    		solve();
    	}
    	return 0;
    }

# 二、双指针 #

双指针只需要两个指针前后移动遍历一遍就可以了，复杂度为O(n)

维护快慢两个指针之间的sum值即可。

循环设计过程：

先判断是否达到截止条件，如果未满足t < S，则进入循环。

（1）如果sum < S,移动快指针一次；

（2）如果sum >= S,维护最小值，并移动慢指针，直到不满足sum >=S为止；

进入下一次循环。

## 代码 ##

#include <iostream>
    
    using namespace std;
    
    int N, S;
    const int MAX_N = 100000;
    int A[MAX_N];
    
    
    void solve()
    {
        
    	int res = N + 1;
    	int sum = 0;
    	int s = 0;
    	int t = 0;
    	
    	while (t < N)
    	{
        
    	    if (sum < S)
    	    {
        
    	        sum += A[t];
    	        ++t;
    	    }
    	    while (sum >= S) 
    	    {
        
    	        res = min(res, t - s);
    	        sum -= A[s];
    	        ++s;
    	    }
    	}
    	
    	
    	if (res == N + 1)
    	{
        
    	    res = 0;
    	}
    	cout << res << endl;
    }
    
    int main()
    {
        
    	int T;
    	cin.tie(0);
    	cout.tie(0);
    	cout.sync_with_stdio(false);
    	
    	cin >> T;
    	
    	while (T--)
    	{
        
    		cin >> N;
    		cin >> S;
    		for (int i = 0 ; i < N; ++i)
    		{
        
    			cin >> A[i];
    		}
    		
    		solve();
    	}
    	return 0;
    }