程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ3061 Subsequence(二分前綴和法+尺取法)

POJ3061 Subsequence(二分前綴和法+尺取法)

編輯：C++入門知識

POJ3061 Subsequence(二分前綴和法+尺取法)

二分+前綴和法

滿足條件的子序列長度在(0,n)之間，sum[x+i]-sum[i]為從從第i個元素開始序列長度為x的元素的和。前綴和可在O(n)的時間內統計

sum[i]的值。再用二分找出滿足條件的最小的子序列長度。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll __int64
#define INF 0x3fffffff
using namespace std;

int sum[100005];
int a[100005];
int n,s;

bool C(int x)
{
    bool flag=false;
    for(int i=0;i=s)
        {
            flag=true;
            break;
        }
    }
    if(flag) return true;
    else return false;
}

int solve()
{
    int l=0,r=n+1;
    while(r-l>1)
    {
        int mid=(l+r)/2;
        if(C(mid)) r=mid;
        else l=mid;
    }
    return r;
}

int main()
{
    int T;
    //freopen("d:\\Test.txt","r",stdin);
    cin>>T;
    while(T--)
    {
        cin>>n>>s;
        for(int i=0;i尺取法
（1）  設置兩個指針s和t，一開始都指向數列第一個元素，此外sum=0,res=0；



（2）  只要sum


（3）  直到sum>=S，更新res=min(res,t-s)；



（4）  將sum減去一個元素，s加1，執行（2）。



上述流程反復地推進區間的開頭和末尾，來求取滿足條件的最小區間。


#include
#include
#include
#include
using namespace std;
int n,m;
int a[100005];

void solve()
{
    int res=n+1;
    int s=0,t=0,sum=0;
    while(true)
    {
        while(tn) res=0;
    cout<>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i