还是写算法进阶指南时写的题了
真题中又出现想过重写,但想了想还是写篇题解吧
这道题两个人轮流开车,一个走右侧最近的,一个走次近的
先找出每个城市开始的最近和次近,可以用set或双链表来做
题目中给定里程数,枚举起点
如果一个城市一个城市的往后倒,肯定会超时
这时考虑倍增优化
f[k][i][j]表示从i出发,k先开车,走2^j天到达的城市
da[][][],db[][][]类似地分别表示两个人的路程
依然枚举起点,倍增找到两人走的路程即可
时间复杂度可降到nlogn
这个代码还是不太好写的,有些细节
最后附上代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
typedef pair<PII,int> PIII;
const int N=1e5+5,inf=0x3f3f3f3f;
int g[2][N],h[N],n,f[20][N][2],da[20][N][2],db[20][N][2],power[22];
set<PII> s1;
void ask(int x,int s,int &la,int &lb)
{
la = lb = 0;
for(int p=19; p>=0; p--){
if(f[p][s][1] && la + lb + da[p][s][1] + db[p][s][1] <= x){
la += da[p][s][1], lb += db[p][s][1];
s = f[p][s][1];
}
}
}
int main()
{
power[0]=1;
for(int i=1;i<=20;i++)
power[i]=power[i-1]*2;
cin >> n;
for(int i=1;i<=n;i++)
scanf("%d",&h[i]);
s1.insert({h[n],n});
s1.insert({h[n-1],n-1});
g[0][n-1]=n;
for(int i=n-2;i>0;i--)
{
priority_queue<PIII> heap;
set<PII>::iterator it = s1.lower_bound({h[i],0});
if(it!=s1.end())it++;
if(it==s1.end())it--;
for(int j=1;j<=4;j++)
{
if( it==s1.begin() ) { heap.push( { { - abs ( (*it).first-h[i] ) , - (*it).first } , (*it).second } ); break; }
heap.push( { {-abs( (*it).first-h[i]) , -(*it).first } , (*it).second }),it--;
}
g[0][i]=heap.top().second;
heap.pop();
g[1][i]=heap.top().second;
s1.insert({h[i],i});
}
for(int i=0;i<20;i++)
{
for(int j=1;j<=n;j++)
{
if(i==0)f[i][j][0]=g[0][j],f[i][j][1]=g[1][j],da[0][j][0] = abs(h[j]-h[g[0][j]]), db[0][j][1] = abs(h[j]-h[g[1][j]]);
else
{
for(int k=0;k<2;k++)
{
if(i==1)
{
f[1][j][k]=f[0][f[0][j][k]][1-k];
da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k];
db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][1-k];
}
else
{
f[i][j][k]=f[i-1][f[i-1][j][k]][k];
da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k];
db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];
}
}
}
}
}
int x0 , ans , ansh = -inf;
double ansval=inf;
cin >> x0;
int start=0,la,lb;
while(++start<=n)
{
ask(x0,start,lb,la);
double nval = (lb == 0 ? inf : (double) la / lb);
if(nval < ansval || (nval == ansval && h[start] > ansh) ){
ansh = h[start], ansval = nval;
ans = start;
}
}
cout<<ans<<endl;
int m;
cin >> m;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&start,&x0);
ask(x0,start,lb,la);
printf("%d %d\n",la,lb);
}
}