ACM 二分 Aggressive cows & 尺取 Subsequence-蒲公英云

ACM 二分 Aggressive cows & 尺取 Subsequence

た入场券 2022-06-12 08:46 270阅读 0赞

滴，集训第三天打卡。

今天是堆，二分和尺取，不过我好像没做到用堆的…

二分的套路是：

while(f<=l)//二分 
{
    mid=(f+l)/2;
    if(hs(mid))//判断中间值是否满足条件
    f=mid+1;
    else
    l=mid-1;
}

尺取法：尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。

int l = 0,w= 0,sum = 0,ans=n+1;
while(1)
{
    while(w < n && sum<s)
    {//从前面开始
        sum+=a[w];
        w++;
    }
    if(sum < s)
    {//条件不满足了；
        break;  
    }
    min = w-l;
    if(min > ans)
    min = ans;
    ans = min;//ans就是最小长度
    sum -= a[l++];//尺取法的前进；
}

POJ 2456 Aggressive cows（二分）

题目大意：FJ 有一个很长的谷仓，然后里面有 N 棚， N 个棚在一条直线上，第 i 个棚的位置为 xi。然后他有 c 只牛，为了防止牛相互攻击，则要找出最大的两只牛之间距离，前提是这 c 只牛都必须能放下。

解题思路：排序谷仓，从第一个出发（第一个肯定选），查找间距为n的是否存在，如果到末尾都满足的话，说明n成立，查找最大的n即可。（我的是在函数里sb里查找是否满足的）

#include <stdio.h>
#include <algorithm>
using namespace std;
int a[100005];
int n,m,i,j,f,l,mid;
bool sb(int mm)
{
    int i,s=1,k=0;
    for(i=1;i<n;i++)
    {
        if(mm+a[k]<=a[i])
        {
            k=i;
            s++;
        }
        if(s==m)
        break;
    }
    if(s<m)return false;
    return true; 
}
int main()
{    
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    sort(a,a+n);
    f=1,l=a[n-1]-a[0];
    while(f<=l)//二分 
    {
        mid=(f+l)/2;
        if(sb(mid))
        f=mid+1;
        else
        l=mid-1;
    }
    printf("%d\n",l);
}

POJ 3061 Subsequence（尺取法）

题目大意：给定长度n的数列整数，以及整数s，求出总和不小于S的连续子序列的长度的最小值。

解题思路：直接用尺取法呀…

#include <stdio.h>
int a[100005];
int main()
{
    long long t,n,s,i,k,sum,f,l,ss,num,nn;
    scanf("%lld",&t);
    while(t--)
    {
        k=0;sum=0;
        scanf("%lld%lld",&n,&s);
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            if(a[i]>=s)
            k=1;
            sum+=a[i];
        }        
        if(k==1)//有单独一个存在可以满足s,则1为最小值 
        printf("1\n");
        else if(sum<s)//如果总合都不够s,则肯定不存在 
        printf("0\n");
        else 
        {
            f=0;l=0;num=n+1;nn=0,ss=0;
            while(f<=l&&l<n)//尺取 
            {
                while(ss<s&&l<n)
                {
                    ss+=a[l];
                    nn++;l++;
                }                                    
                while(ss>=s&&f<n)
                {
                    if(nn<num)
                    num=nn;
                    ss-=a[f];
                    f++;
                    nn--;
                }                
            }
            if(num!=n+1)
            printf("%lld\n",num);
            else
            printf("0\n");
        }
    }
}