2018.2.4 二分考试专题

考试

首先先上二分答案的基础板子吧

while(l<=r)
{
    rg ll mid=(l+r)>>1;
    if(check(mid))ans=mid,r=mid-1;
    else l=mid+1;
}

本次考试排名:Rank3
本次考试题目推荐:跳跳棋(标签：倍增/二分)

1.简单题

题面描述

给你一个有 n 个正整数元素的数列,要求把它划分成k段,使每段元素和的最大值最小,求出这个目标值。

数据范围

30%数据 n <= 30, k <= 10
100%数据 n <= 100000, k <= n, 0<=ai <= 10^9

心路历程

表示刚开始写时脑海中蹦出了一个O(n^2*k)的dp[i][j][0/1]，表示前i个元素划分成j段且第i个元素是否新开一个段所需的每段元素和最大值。后来发现完全不行，不仅复杂度过不去，而且貌似还有很多细节会出错。

解法

于是我开始冥思苦想（而此时yyb大佬说这题我五分钟能切)了半小时，终于想出来了这个世纪大难题。果不其然，还是被我想出来了。

二分答案，二分出每段元素和的最大值mid，然后关键是check，这里就要利用贪心的思路，从1开始扫到n，只要现在某一段的和没有爆掉标准mid，那就加，加不了就新开一段。(这很明显是对的)

好了，上代码

bool check(ll stand)
{
    rg ll sum=0,cnt=0;
    for(rg int i=1;i<=n;i++)
    {
        if(sum+a[i]>stand){sum=0;cnt++;}
        if(cnt>k-1)return 0;
        sum+=a[i];
    }
    //printf("此时标准为%lld能通过\n",stand);
    return 1;
}

2.软件开发

题目描述

一个软件开发公司同时要开发两个软件,并且要同时交付给用户,现在公司为了尽快完成这一任务,将每个软件划分成m个模块,由公司里的技术人员分工完成,每个技术人员完成同一软件的不同模块的所用的天数是相同的,并且是已知的,但完成不同软件的一个模块的时间是不同的,每个技术人员在同一时刻只能做一个模块,一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序,求出公司最早能在什么时候交付软件。

数据范围

20%的数据 1≤n,m≤10
40%的数据 1≤n,m≤20
100%的数据 1≤n,m,d1,d2≤100

心路历程

真的悲伤!打完第一题之后就颓了半小时，这题一开始推了一波没有什么用处的公式，以为${m}^{n}$的复杂度是能过的，果然还是我太天真了

$$\quad\sum_{i=1}^{n}x_i*(p_i-q_i)+mid*\sum_{i=1}^{n}q_i\ge m*(P+Q)$$
上面这个公式若满足，则证明我二分出的mid是合理的($x_i$为天数)，但是要实现简直超难(还不如打搜索)

解法

于是我在ljq大佬的提示下，瞬间知道这个题目怎么做了

dp[i][j]表示前i个人做j个一软件的模块所剩余时间能做的最大的二软件的数目这样check就非常方便了，只需 $dp[n][m]\ge m$ 就证明二分出的答案合理，至于转移方程则为$dp[i][j]=max{dp[i-1][j-k]+(mid-a[i]*k)/b[i]}$
此外还有一些细节
1. $k\leq j$且$mid\ge a[i]*k$
2. $memset(dp,-0x3f,sizeof(dp))$，以防不合法答案出现

好了，上代码

bool check(int stand)
{
    memset(dp,-0x7f,sizeof(dp));
    dp[0][0]=0;
    //cout<<stand<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=j;k++)
            {
                if(stand<a[i].d1*k)continue;
                dp[i][j]=max(dp[i][j],dp[i-1][j-k]+(stand-a[i].d1*k)/a[i].d2);
            }
        }
    }
    if(dp[n][m]>=m)return 1;
    else return 0;
}

跳跳棋

题面描述

跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏:棋盘上有 3 颗棋子,分别在 a,b,c 这三个位置。我们要通过最少的跳动把他们的位置移动成 x,y,z。
(棋子是没有区别的)跳动的规则很简单,任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。写一个程序,首先判断是否可以完成任务。如果可以,输出最少需要的跳动次数。

数据范围

20% 输入整数的绝对值均不超过 10
40% 输入整数的绝对值均不超过 10000
100% 绝对值不超过 10^9

心路历程

离考试下考还有30min，之前做完第二题后开始摆，真的搞笑，题目连看错两次，一次只能越过一个棋。意识到正解用什么方法时马上就要下考了，于是又开始颓(有点后悔)。不摆的话就不会没有时间继续想正解了。嗯，算作一次经验吧。至于暴力分太久没打过了，BFS很不优秀，只有15分，而别人的BFS有35分，加油练搜索吧!

解法

对于每一个状态，其实顶多就三种状态转移(a,b,c)
设s1=b-a，s2=c-b;
1.b往a跳
2.b往c跳
3.若s1 > s2，则只能c往b跳，若s1 < s2,则只能a往b跳
(若s1==s2则没有第三种情况)
因而可看成一棵状态树，S能够走到T的充要条件是S和T在同一棵树中(根节点为s1==s2)，因而我们需要找回S和T的根，于是通过类似辗转相除法的原理得到S和T的根，再算LCA就好了，S到T要经历的次数，其实就是让你求树上两点间最短路。
那为什么还要使用二分呢？(其实倍增也可以)
因为我们如果使用倍增则需要构出一颗完整的二叉树，这又比较麻烦，则我们考虑二分要跳的步数，然后check就可以了!

好了，放代码(参考资料 wfj_2048)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define rg register
#define inf 1e9
int a[5],b[5];
int S,T;
struct hand{int a,b,c;};
bool operator !=(hand A,hand B)
{
    if(A.a!=B.a||A.b!=B.b||A.c!=B.c)return 1;
    return 0;
}
hand find(hand u,int k,int &dep)
{
    int t,dis1=u.b-u.a,dis2=u.c-u.b;
    if(dis1==dis2)return u;
    if(dis1<dis2)
    {
        t=min(k,(dis2-1)/dis1);
        k-=t;
        dep+=t;
        u.a+=t*dis1;
        u.b+=t*dis1;
    }
    else
    {
        t=min(k,(dis1-1)/dis2);
        k-=t;
        dep+=t;
        u.b-=t*dis2;
        u.c-=t*dis2;
    }
    if(k)return find(u,k,dep);
    else return u;
}
int depa,depb;
int main()
{
    for(int i=1;i<=3;i++)cin>>a[i];sort(a+1,a+4);
    for(int i=1;i<=3;i++)cin>>b[i];sort(b+1,b+4);
    hand x=(hand){a[1],a[2],a[3]};
    hand y=(hand){b[1],b[2],b[3]};
    hand u=find(x,inf,depa),v=find(y,inf,depb);
    if(u!=v)
    {
        puts("NO");
        return 0;
    }
    if(depa<depb)swap(x,y),swap(depa,depb);
    int l=0,r=depb,cnt,ans;
    x=find(x,depa-depb,cnt);
    while(l<=r)
    {
        int mid=(l+r)>>1;
        hand xx=find(x,mid,cnt),yy=find(y,mid,cnt);
        if(xx!=yy)l=mid+1;
        else ans=mid,r=mid-1;
    }
    puts("YES");
    printf("%d\n",ans*2+depa-depb);
    return 0;
}

OK，今天的题目于2.5搞完总结了，以后一定要坚持！