发布于

解题报告 P1182 数列分段 Section II

题目内容

P1182

大意：给出一个序列，要求分成 m 段，求每段和的最大值的最小值

解题思路

一看到“最大的最小”就知道这题需要使用二分答案。首先判断他的单调性：很明显，我们如果设定每段和的最大值越大，需要划分的段数就越小，相反的，如果我们设定每段和的最大值越小，需要划分的段数就越多，以此性质来进行二分答案。

至于如何判断，就需要使用前缀和，具体见代码的 check 函数。

#include <cstdio>

const int maxn=1e5+5;
int n,m,a[maxn],sum[maxn];

bool check(int mid)
{
    int cnt=0,lastans=1;//cnt为切的刀数，lastans为新一段的起点
    for(int i=1;i<=n;i++)//开始扫描
    {
        if(sum[i]-sum[lastans-1]>mid)//如果[lastans,i]的和大于设定的最大值
        {
            cnt++;//那么就只取[lastans,i-1]
            lastans=i;//i成为新的lastans
        }
    }
    return cnt+1<=m;//由于cnt是刀数，判断的时候要+1
}

int main()
{
    scanf("%d %d",&n,&m);
    int maxa=0;//序列中元素的最大值，以此为左端点进行二分
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        sum[i]=sum[i-1]+a[i];
        maxa=maxa<a[i]?a[i]:maxa;
    }
    int l=maxa,r=sum[n],ans;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))//如果能行，就说明mid可以再小一点
        {
            ans=mid;
            r=mid;
        }
        else
            l=mid+1;
    }
    printf("%d\n",ans);
}

总的时间复杂度为 O(n\log n)

发布于

解题报告 P1083 借教室【NOIP2015TGD2T2】

题目内容

P1083

解题思路

嗯，这道题一看，暴力枚举

分析：这道题满足二分答案，为什么：

我们将订单挨个标号，很显然，订单越多，越难满足要求，这满足二分答案要求的单调性。我们只需将订单挨个枚举即可。

二分的答案是订单的标号，订单越多越到后面越不能满足，因此很容易找到那个”1″和”0″的分界，使用一个check函数即可判断。

至于check函数的实现，这里使用了差分的重要思想。每一个订单会给出起始时间s和末尾时间t，相当于在[s,t]这段时间内多租借d个教室，很像区间加问题。所以我们定义一个数组c存储需要使用的教室的差分，处理每个订单的时候就c[s[i]]+=d[i],c[t[i]+1]-=d[i]。注意是t[i]+1，并且是-=，已掉坑不止5次。然后将差分数组加起来（求前缀和）判断这么多个订单能否满足能提供教室的条件，返回即可。

代码实现：

#include <cstdio>
#include <cstring>
#define f(i,a,b) for(int i=a;i<=b;++i)

const int maxn=1e6+5;
int n,m,r[maxn],d[maxn],s[maxn],t[maxn],diff[maxn];//r,d,s,t见题意，diff为差分数组

inline int read()//我喜欢快读
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

bool check(int mid)
{
    memset(diff,0,sizeof(diff));//每次使用的时候要清零差分数组
    f(i,1,mid)
        diff[s[i]]+=d[i],diff[t[i]+1]-=d[i];//操作差分数组实现区间加
    int ans=0;//记录前缀和
    f(i,1,n)
    {
        ans+=diff[i];//每次加起来
        if(ans>r[i])//如果不能满足需要
            return 0;
    }
    return 1;//否则return true
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    n=read(),m=read();
    f(i,1,n)
        r[i]=read();
    f(i,1,m)
        d[i]=read(),s[i]=read(),t[i]=read();
    //以上读入数据
    int l=1,r=m;//开始二分
    while(l<r)//mid越大越难不挨卡
    {
        int mid=l+r>>1;
        if(check(mid))//如果满足要求
            l=mid+1;//说明mid可能还可以更大
        else
            r=mid;//否则mid就太大了
    }
    if(r!=m)//如果r!=m的话说明不能满足所有订单
        printf("-1\n%d\n",r);
    else//否则可以满足所有订单
        printf("0\n");
    return 0;
}

反思

蓝题，果然在二分的思维比较难，而且二分答案的代码细节非常多。

下次再写一波

发布于

解题报告 P2678 跳石头

题目内容

P2678 跳石头

解题思路

跳石头这道题显然满足单调性和有界性，可以用二分答案求解

枚举题目要求的最短跳跃距离，思考：最短跳跃距离越大，需要挪走的石头越多，这显然满足单调性，又由于能挪走的石头有一个上限M，因此可以使用二分答案进行求解。

求解时从区间[1,L]开始二分，取中点mid，然后开始模拟跳石头，如果下一个石头离上一个石头的距离小于了取的mid，则说明这块石头应该被挪走，计数器cnt加一

如果中途时cnt大于了M，说明需要挪走的石头数量超过了上限，即mid取的过大，方案不可行，接下来就继续二分[1,mid-1]，一步步缩小二分的范围。

同理，如果结束时cnt\leq M，说明该方案可行，但是可能不是最优解，mid还可以取更大，因此继续二分[mid,L]，依次求解。

到最后如果到了区间[l,r]且l=r，说明已经找到了最优解，输出即可。

#include <cstdio>

int L,n,m,d[50005];//见题意

bool judge(int x)
{
    int cnt=0;//表示需要挪多少块石头
    int now=0,i=0;//now表示当前人在的石头标号，i表示当前处理的石头标号
    while(i<n+1)//注意是n+1
    {
        ++i;
        if(d[i]-d[now]<x)//如果两块石头中间的距离小于需要查找的mid值
            cnt++;
        else
            now=i;
    }
    return cnt<=m;//返回判断结果
}

int binary()//二分答案
{
    int l=1,r=L;//表示二分边界
    int ans;//当前答案
    while(l<=r)//当l<=r的时候
    {
        int mid=l+r>>1;//用位运算更快？？？
        if(judge(mid))//如果这个满足条件
            ans=mid,l=mid+1;//那么把它存下来，更新二分边界
        else//如果不满足条件的话
            r=mid-1;//mid取太大了，更新二分边界
    }
    return ans;//返回答案
}

int main()
{
    scanf("%d %d %d",&L,&n,&m);
    d[0]=0;
    for(int i=1;i<=n;i++) scanf("%d",d+i);
    d[n+1]=L;
    printf("%d\n",binary());
    return 0;
}

反思

二分答案，当题目中有最大的最小或者最小的最大时一般就可以使用，需要条件满足单调性和有界性。

比如这个跳石头，跳的最短距离越大需要挪走的石头越多，就可以使用二分答案枚举答案求解

然鹅我还是不会二分答案