UOJ 49 【UR #3】铀仓库

#49. 【UR #3】铀仓库

统计

顽皮的小O潜入了著名核物理专家 Picks 的研究所，走进了存放浓缩铀的仓库。

浓缩铀存放在一个个箱子里，一共有

小O脑洞大开，决定进行一项游戏。他会先选择一个整数坐标

这段时间内他的行动方式包括：

向左移动单位
向右移动单位
如果现在手上是空的，那么可以从当前位置拿起一个装有浓缩铀的箱子，瞬间完成。
如果现在拿着一个装有浓缩铀的箱子，那么可以把这个箱子放在当前位置所有箱子的顶部，瞬间完成。

由于小O很小，任意时刻他只能拿着至多一个箱子。他希望进行至多

请你帮小O计算，他如果

（PS：危险动作，请勿模仿。）

输入格式

第一行两个整数

第二行

第三行

输出格式

一行一个非负整数，表示位置

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

2 3
1 2
2 3

output

样例二

input

9 15
2 3 5 7 11 13 17 23 29
4 5 4 1 2 4 6 1 3

output

样例三

见样例数据下载。

限制与约定

测试点编号	数据规模	特殊限制
1
2
3
4
5
6
7
8
9
10

对于全部数据，均有

时间限制：

空间限制：

下载

样例数据下载

如果选定了堆积位置，那么一定是选距离这个位置近的积木往这儿堆

二分答案mid

计算在某个位置堆mid个积木的最少花费时间

计算时，先算出往位置1堆mid个积木要用的区间[l,r]

那么随着堆积位置的右移，这个所用区间也右移

那么就根据l，r 到当前堆积位置的距离，判断区间是否需要右移，直到区间不能右移、、

然后计算这个区间里的积木移到堆积位置的时间

列个式子合并同类项就可以很快算出来了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500001
using namespace std;
typedef long long LL;
int n;
LL t,pre[N],sum[N],a[N],siz[N],x[N];
LL read(LL &x)
{
    x=0; char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0' && c<='9') { x=x*10+c-'0'; c=getchar(); }
}
void print(LL ans)
{
    if(ans/10) print(ans/10);
    putchar(ans%10+'0');
}
LL cal(int mid,int l,int r)
{
    LL tmp=0;
    tmp+=pre[r]-pre[mid]-x[mid]*(sum[r]-sum[mid]);
    tmp+=x[mid]*(sum[mid-1]-sum[l-1])-pre[mid-1]+pre[l-1];
    tmp-=(a[r]-siz[r])*(x[r]-x[mid]);
    tmp-=(a[l]-siz[l])*(x[mid]-x[l]);
    return tmp<<1;
}
bool check(LL mid)
{
    memset(siz,0,sizeof(siz));
    int l=1,r=0; 
    while(mid)
    {
        r++; 
        siz[r]=min(a[r],mid);
        mid-=siz[r];
    }
    if(cal(1,l,r)<=t) return true;
    LL tmp;
    for(int i=2;i<=n;i++)
    {
        while(x[r]-x[i]<x[i]-x[l])
        {
            if(siz[r]==a[r])
            {
                if(r<n) { r++; continue; }
                break;
            }
            tmp=min(a[r]-siz[r],siz[l]);
            siz[r]+=tmp; 
            siz[l]-=tmp;
            if(!siz[l]) l++;
        }
        if(cal(i,l,r)<=t) return true;
    }
    return false;
}
int main()
{
    scanf("%d",&n); read(t);
    for(int i=1;i<=n;i++) read(x[i]);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) 
    {
        sum[i]=sum[i-1]+a[i];
        pre[i]=pre[i-1]+x[i]*a[i];
    }
    LL l=0,r=sum[n],mid,ans=0;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    print(ans);
}