题解：P1798 的二分答案做法

· · 题解

发现没有二分答案的方法，提交一篇题解。

题目描述

传送门

正题

首先，类似于 P1007，将两人相遇的情况忽略。

此时，给每人增加一单位时间，他们搬到的箱子并不会因此减少（而且有可能增多），也就是说，搬箱子的个数满足单调性。

所以，考虑二分答案。

假如我们现在有 t 分钟来搬运箱子，那么如何计算出一个人可以搬运的箱子数量呢？
先将初始时的状态恢复成在 1 楼，刚搬起一个新的箱子的状态，这需要一段时间。
然后，在此状态下，每搬一个箱子并回到 1 楼的时间就是 2(n-1) 分钟（上下楼都为 n-1 分钟），直接将剩下的时间除以这个时间并下取整就可以了。

如何计算初始时状态恢复的时间？

分两种情况讨论。

  1. 如果这个人正在往上搬箱子，那么需要 n-1 分钟来从上往下，要 n-now 分钟来从下往上（now 表示现在所处的楼层），共为 2\times n -1-now 分钟。
  2. 如果这个人在往下走，那么需要 now-1 分钟来回到 1 楼。（now 表示现在所处的楼层）

上述计算是 O(1) 的，所以 check 函数的复杂度是 O(n)。

一个细节

只要箱子到了就行了，不用人回到 1 楼，所以可用时间要增加 n-1，以保证答案正确（因为上述计算的箱子数保证了人搬完这些箱子还能回到 1 楼，但实际上不需要）

这样，这个题就做完了。时间复杂度为 O(n\log{val})，val 为二分上界。
空间复杂度为 O(n)。

二分上界

显然，只有一个人的时候，时间最长，最长约为 n\times m（由于这个人可以手上拿着箱子，所以实际使用时需要略大），即 10^{18}。所以本解法的运行速度略慢（时间约为 3 倍），但可以通过。

代码

#include<bits/stdc++.h>

using namespace std;

struct man//存人的数组
{
    int now;int type;
}men[500001];

long long n,k,m;

bool check(long long now)//可行返回true
{
    long long ans=0;//答案可能爆 int
    for(int i=1;i<=k;i++)
    {
        ans+=(now+
        n-1-//额外的时间，见上
        (men[i].type==1?(men[i].now-1):(2*n-1-men[i].now))//恢复时间
        )/(2*n-2);
    }
    //cout<<now<<' '<<ans<<'\n';
    return ans>=m;//如果搬了 m 个箱子就够了
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);//优化读入
    cin>>n>>k>>m;
    for(int i=1;i<=k;i++)cin>>men[i].now>>men[i].type;
    long long l=0,r=1e18+1e10;//略微开大一点
    while(l<r-1)
    {
        long long mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid;
    }
    cout<<r;
    return 0;
}