ACM 二分 Aggressive cows & 尺取 Subsequence

た入场券 2022-06-12 08:46 175阅读 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（二分）**

**![20170720102138369][]**

题目大意**：**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（尺取法）

**![20170720104746925][]**

题目大意：给定长度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");
    		}
    	}
    }

[20170720102138369]: /images/20220612/f2d12cfdc5da463babb8d520140f7b08.png
[20170720104746925]: /images/20220612/e9716ec2f8f8430695c589edf875e6ae.png