【算法练习】尺取法——答案

这是答案！！！没做不要抄（去这里看题目做）

第一题（求和为C）

#include<bits/stdc++.h>
using namespace std;
int n,c,a[100005],k,ans;
int main(){
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
		cin>>a[i];
    }
    k=k+a[1]; 
    for(int x=1,y=2;y<=n;y++)
	{
        k+=a[y];
		while(k>c)
        {
            k-=a[x++];
        }
		if(k==c && y-x>0) ans++;   
    }
    cout<<ans;
    return 0;
}

第二题（黑白奶牛）

#include<bits/stdc++.h>
using namespace std;
int sum[100001];
int t,l,r,s,ans=0;
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>t;
        if(t==0) sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1];
    }
    l=r=0;
    while(r<=n)
    {
        s=sum[r]-sum[l-1];
        if(s<=k)
        {
            ans=max(ans,r-l+1);
            r++;
        }
        else l++;
    }
    cout<<ans;
    return 0;
}

第三题（连续子序列）

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],s[100005],mi=INT_MAX,sum,i=1,j;
long long ss;
int main()
{
    cin>>n>>ss;
    for(int x=1;x<=n;x++)
    {
    	cin>>a[x];
        sum+=a[x];
        s[x]=s[x-1]+a[x];
        if(sum>=ss) sum=INT_MIN,j=x;
    }
    for(;j<=n;)
    {
        if(s[j]-s[i-1]>=ss) mi=min(j-i+1,mi),i++;
        else j++;
        if(i==j) j++;
    }
    if(mi==INT_MAX)mi=0;
    cout<<mi;
    return 0;
}

第四题（射箭） 

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],s[2005],minn=INT_MAX,ans;
int main(){
    cin>>n>>m;
    for (int i = 1;i<=n;i++)
	{
        cin>>a[i];
    }
    int l=1,r=1; 
    for (;r<=n;r++)
	{
        s[a[r]]++;
        if (s[a[r]]==1) ans++;
        while(ans>=m)
		{
            minn=min(minn,r-l+1);
            s[a[l]]--;
            if(s[a[l]]==0) ans --;
            l++;
        }
    }
    if (minn==INT_MAX) minn=-1;
    cout<<minn;
    return 0;
}

第五题（最短序列）

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],k,ans=INT_MAX;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]=(1-a[i])+a[i-1];
    }
    int l=1,r=1;
    for(;r<=n;r++)
    {
        while(a[r]-a[l-1]>=k)
        {
            ans=min(ans,r-l+1);
            l++;
        }
    }
    if(ans==INT_MAX) ans=0;
    cout<<ans;
    return 0;
}

第六题（唯一的雪花（一））

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n,a[1000005],b[1000005],ans=0,s;
signed main(){
    cin>>t;
    while(t--)
    {
        
        cin>>n;
        ans=0,s=0;
        for(int i=1;i<=1000000;i++) a[i]=0;
        for(int i=1;i<=1000000;i++) b[i]=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }    
        int l=1,r=1;
        for(;r<=n;r++)
        {
            b[a[r]]++,s++;
            while(b[a[r]]>1)
            {
                b[a[l]]--,l++,s--;
            }
            ans=max(ans,r-l+1);
        }
        cout<<ans<<"\n";
    }
    return 0;
}

不会的私聊我哈！