【问题描述】
小 OY 是一个喜欢搭积木的孩子,他有一天决定向小 C 展示他特别的搭积木
技巧。
现在一条直线上从左到右有 n 个位置,标号 1..n,第 i 个位置坐标为 x_i。
每个位置上都预先叠好了一些积木,其中第 i 个位置上叠了 a_i 块积木。
小 OY 一开始会向小 C 指定 1..n 中的某个位置 s,然后,他在第 0 秒从位置
s 出发,开始搭积木。
他可以做这些动作:
1、向左移动 1 个单位坐标,用时 1 秒。
2、向右移动 1 个单位坐标,用时 1 秒。
3、从当前位置顶部拿起一块积木,瞬间完成。
4、把拿着的积木叠到当前位置,瞬间完成。
由于小 OY 很小,任意时刻他手上至多只能带一块积木。
当时间到达第 T 秒时,小 OY 不会再进行移动。这时候,如果位置 s 的积木
叠得越高,就显得小 OY 叠积木本领越强。
现在,小 OY 在思考,如果他的移动策略足够高明,并且位置 s 也选定得恰
到好处,那么第 T 秒时位置 s 最多能叠到多少块积木呢?
【输入】
输入文件名:block.in
第一行两个数 n、T。
第二行 n 个严格递增的整数,第 i 个数为 x_i。
第三行 n 个非负整数,第 i 个数为 a_i。
【输出】
输出文件名:block.out
第一行一个数,为从最优的 s 出发在最高明的移动策略下,第 T 秒位置 s 至
多能叠到多少块积木。
【数据范围】
测试点 1..3:n≤100,T≤1000
测试点 4..5:a_i≤1
测试点 6..7:x_i = i
测试点 1..8:n≤10 5
测 试点 1..10: 1≤n≤ 5*10 5 ,0≤ T≤ 10 18 ,0≤ a_i≤10 4 ,0 ≤ x_i≤10 9
算法 1
先枚举 s,然后从近到远把其他位置的积木一个个拿到 s 来,直到时间 T 耗尽
为止。复杂度 O(nT)。
算法 2
优化一下算法 1,假设当前取到的最左、最右位置分别为 l、r,然后每次一下
取 min(a[l],a[r])个,如果取完后时间不超过 T 就取完,否则直接计算还能取几
个。由于每次左右指针都至少有一个会往边界移,复杂度 O(n^2)。
算法 3
先二分答案 k,问题成了:求把位置 s 叠到高度 k 所需的最短时间。
从左到右枚举 s,那么肯定是从前 k 近的地方搬来积木。我们想象每个位置 i
的 a[i]个积木是从左到右紧密排列在坐标 x[i]的,令 l 表示前 k 近的积木最左的
那块,r 表示最右的那块,随着 s 的右移,左边的积木们越来越远,右边的越来越
近,那么 l、r 是非降的。
暴力移动指针的话,复杂度是 O(Σ a[i])的。
正解：
在算法3的基础上如果时间不超过就尽可能取完，因为l,r非降，所以可以用
类似单调队列的思想，移动左右
lc表示a[l]未取的积木，rc表示a[r]已取的积木
先得出把1堆到k的最短时间，得到r和rc
之后考虑把s位置右移，右移后在不考虑l,r的移动的情况下
等价于把1～i的积木右移，i+1～r的积木向右撤回
移动完更新时间后，如果l比r距离s远，那么不如把l积木不取，来取r的积木
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int n;
ll a[],x[];
ll s[],T,ans;
ll sum(int l,int lc,int r,int rc)
{
if (l==r)
return rc-lc;
return (s[r-]-s[l]+a[l]-lc+rc);
}
bool check(ll need)
{int i;
int l=,r=n+;
ll lc=,rc=;
ll s=;
ll cur=;
for (i=;i<=n;i++)
{
if (s+a[i]<=need)
{s+=a[i];cur+=(x[i]-x[])*a[i];}
else
{
rc=need-s;r=i;cur+=(x[i]-x[])*rc;
break;
}
}
if (cur<=T) return ;
for (i=;i<=n;i++)
{
cur+=(x[i]-x[i-])*(sum(l,lc,i,)-sum(i,,r,rc));
while (r<=n&&(x[i]-x[l])>(x[r]-x[i]))
{
int p=min(a[l]-lc,a[r]-rc);
cur+=(x[r]-x[i]-x[i]+x[l])*p;
lc+=p;rc+=p;
if (lc>=a[l]) l++,lc=;
if (rc>=a[r]) r++,rc=;
}
if (cur<=T) return ;
}
return ;
}
int main()
{int i;
cin>>n>>T;
T/=;
for (i=;i<=n;i++)
{
scanf("%lld",&x[i]);
}
for (i=;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-]+a[i];
}
ll l=,r=s[n];
while (l<=r)
{
ll mid=(l+r)/;
if (check(mid)) ans=mid,l=mid+;
else r=mid-;
}
cout<<ans;
}