确实是个好题但码量咋这么大,是我写的丑吗
好,假设众所周知如何$O(nlogn)$地求出$A,B$在某个位置开一次车走到的位置.如果不存在,就设为0.
为了方便,记g1[i]表示i之后最近的点,也就是B开一次车到的地方,g2[i]表示i之后次近的点,也就是A开一次车到的地方
先考虑朴素的做法.
设calc_dis(x,s)
函数返回$i$在路程不超过$x$的情况下$A$走的距离$disa,B$走的距离$disb$
我们可以这样实现:
初始化$disa=disb=0$
如果是$A$开车,但不存在下一个点,或走了会导致路程超过$x$,即当g2[s]==0
或disa+disb+abs(a[s]-a[g2[s]])>x
就结束.
否则,就让$A$开一次车,disa+=abs(a[s]-a[g2[s]]),s=g2[s]
,然后下一次让$B$开.
$B$的情况同理.这样,我们就在$O(n)$的时间内求出了$i$在路程不超过$x$的情况下$A$走的距离$disa,B$走的距离$disb$.
对于问题1,枚举每一个点$i$作为起点,每次调用calc_dis(x,i)
,更新答案.
对于问题2,直接调用就好了.
这样的时间复杂度是$O((n+m)n)$就可以拿到70pts了.
考虑进一步优化计算calc_dis(x,s)
使用倍增,先预处理f[k][i][j]表示k先开车(0表示A,1表示B),从j城市开始,开了2^i天到达的城市
- $i=0:f[0][i][j]=g2(j),f[1][i][j]=g1(j)$,即开一次车
- $i=1:f[k][i][j]=f[!k][i-1][f[k][i-1][j]]$,即k开一天,然后另一个人再开一天
- $otherwise:f[k][i][j]=f[k][i-1][f[k][i-1][j]]$,即k开$2^{i-1}$天,由于是偶数,k再开$2^{i-1}$天.
接下来预处理da[k][i][j]表示k先开车,从j开始开了2^i天,a所走的距离
- $i=0:da[0][i][j]=dist(j,g2(j)),da[1][i][j]=0$,即a开车,或不开车
- $i=1:nxt=f[0][i][j],da[0][i][j]=da[0][i-1][j]+da[1][i-1][nxt]$,即a开一天,然后B开一天.
- $otherwise:nxt=f[0][i][j],da[0][i][j]=da[0][i-1][j]+da[0][i-1][nxt]$即a开$2^{i-1}$天,由于是偶数,a再开$2^{i-1}$天.
同理,预处理db[k][i][j]表示k先开车,从j开始开了2^i天,b所走的距离
接下来我们就可以在$O(logn)$的时间内计算calc_dis(x,s)
了:
倒序枚举$i$,如果存在$2^i$天之后到达的城市,且走了之后距离之和不超过限制,那就$s=f[0][i][s]$,然后更新a,b所走的距离,直到$i<0$就结束.
最后时间复杂度$O((n+m)logn)$
PS:求最小比值那里,我本来想用乘法代替除法避免浮点数,结果..爆long long了..于是只能用double了.
贴代码:
/**********/省略快读
#define MAXN 100011
#define MAXL 19
ll a[MAXN],n,g1[MAXN],g2[MAXN],da[2][MAXL][MAXN],db[2][MAXL][MAXN];
ll f[2][MAXL][MAXN];
ll l[MAXN],r[MAXN],p[MAXN];//链表求g1(i),g2(i)
struct node
{
ll val,dex;
bool operator <(const node& t)
const
{
return val<t.val;
}
}fx[MAXN];
void del(ll x)
{
r[l[x]]=r[x];l[r[x]]=l[x];
}
void calc_g()
{
for(ll i=1;i<=n;++i)
{
fx[i].val=a[i],fx[i].dex=i;
l[i]=i-1;r[i]=i+1;
}
l[1]=r[n]=0;
std::sort(fx+1,fx+n+1);
for(ll i=1;i<=n;++i)p[fx[i].dex]=i;
for(ll i=1;i<=n;++i)
{
node pre=fx[l[p[i]]],nxt=fx[r[p[i]]];
if(!pre.dex)
{
if(!nxt.dex)g1[i]=g2[i]=0;
else
{
g1[i]=nxt.dex,g2[i]=0;
nxt=fx[r[r[p[i]]]];
if(nxt.dex)g2[i]=nxt.dex;
}
}
else if(!nxt.dex)
{
g1[i]=pre.dex,g2[i]=0;
pre=fx[l[l[p[i]]]];
if(pre.dex)g2[i]=pre.dex;
}
else
{
if(a[i]-pre.val<=nxt.val-a[i])g1[i]=pre.dex,pre=fx[l[l[p[i]]]];
else g1[i]=nxt.dex,nxt=fx[r[r[p[i]]]];
if(!pre.dex||(nxt.dex&&a[i]-pre.val>nxt.val-a[i]))g2[i]=nxt.dex;
else g2[i]=pre.dex;
}
del(p[i]);
}
}
void prework()//预处理倍增
{
for(ll i=1;i<=n;++i)f[0][0][i]=g2[i],f[1][0][i]=g1[i];
for(ll k=0;k<=1;++k)
for(ll i=1;i<=n;++i)
f[k][1][i]=f[!k][0][f[k][0][i]];
for(ll k=0;k<=1;++k)
for(ll i=2;i<MAXL;++i)
for(ll j=1;j+(1<<i)<=n;++j)
f[k][i][j]=f[k][i-1][f[k][i-1][j]];
for(ll i=1;i<=n;++i)
{
da[0][0][i]=abs(a[i]-a[g2[i]]);
da[1][0][i]=0;
db[0][0][i]=0;
db[1][0][i]=abs(a[i]-a[g1[i]]);
}
for(ll k=0;k<=1;++k)
for(ll i=1;i<=n;++i)
{
ll nxt=f[k][0][i];
da[k][1][i]=da[k][0][i]+da[!k][0][nxt];
db[k][1][i]=db[k][0][i]+db[!k][0][nxt];
}
for(ll k=0;k<=1;++k)
for(ll i=2;i<MAXL;++i)
for(ll j=1;j+(1<<i)<=n;++j)
{
ll nxt=f[k][i-1][j];
da[k][i][j]=da[k][i-1][j]+da[k][i-1][nxt];
db[k][i][j]=db[k][i-1][j]+db[k][i-1][nxt];
}
}
pll calc_dis(ll x,ll s)//如上所述,关键部分
{
ll disa=0,disb=0;
for(ll i=MAXL-1;i>=0;--i)
if(f[0][i][s]&&disa+disb+da[0][i][s]+db[0][i][s]<=x)
{
disa+=da[0][i][s],disb+=db[0][i][s];
s=f[0][i][s];
}
return pll(disa,disb);
}
const double eps=1e-7;//浮点数精度
bool equal(double a,double b)
{
return a+eps>b&&b+eps>a;
}
int main()
{
n=read();
for(ll i=1;i<=n;++i)a[i]=read();
calc_g();
prework();
ll s,x=read(),ans=0,flag=0;
double ansval=0;
for(ll i=1;i<=n;++i)
{
pll res=calc_dis(x,i);
//a/b<disa/disb
if(!res.second&&flag)continue;
if(!flag||((double)res.first/res.second+eps<ansval||(equal((double)res.first/res.second,ansval)&&a[i]>a[ans])))
{
flag=res.second;
ans=i;
ansval=(double)res.first/res.second;
}
}
printf("%lld\n",ans);
ll m=read();
for(ll i=1;i<=m;++i)
{
s=read(),x=read();
pll res=calc_dis(x,s);
printf("%lld %lld\n",res.first,res.second);
}
return 0;
}
#orz