题解 P1081 【开车旅行】

主要分为两个部分：预处理和倍增求解 ## 预处理 主要的难题是预处理出当前城市的最近和次近城市，n^2的暴力枚举显然会超时。下面是巧妙的正解： 先按照城市的高度进行排序，不管位置。排序后用双向链表链接各个城市。再按照原来的顺序，也就是按照原来城市的位置顺序进行预处理。排序后，显然，最近和次近一定在i-2，i-1，i+1，i+2中。得出了最近和次近后，就把当前城市删掉，这样后面扫到的所有城市，都不可能出现其他城市在当前城市西边的情况。 ## 倍增 用fa[i][j]表示a从j出发走2^i天行驶的路程，fb[i][j]表示b从j出发走2^i天行驶的路程。然后，一直逼近就行了 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,l,r,j; struct node { int i, v, l, r; }d[100005]; int h[100005], p[100005]; int fa[100005][21], fb[100005][21], f[100005][21]; int na[100005],nb[100005],a,b,ans=n; double minn=1000000000; bool cmp(node x,node y) { return x.v<y.v; } bool dir() { if(!l) return 0; if(!r) return 1; return d[j].v-d[l].v<=d[r].v-d[j].v; } int pd(int a, int b) { if(!a) return d[b].i; if(!b) return d[a].i; if(d[j].v-d[a].v<=d[b].v-d[j].v) return d[a].i; return d[b].i; } void st() { for(int j=1;j<=20;j++) { for(int i=1;i<=n;i++) { f[i][j]=f[f[i][j-1]][j-1]; fa[i][j]=fa[i][j-1]+fa[f[i][j-1]][j-1]; fb[i][j]=fb[i][j-1]+fb[f[i][j-1]][j-1]; } } } void get(long long x, int p) { a=b=0; for(int i=20;i>=0;i--) { if(f[p][i] && (long long)(a+b+fa[p][i]+fb[p][i])<=x) { a+=fa[p][i]; b+=fb[p][i]; p=f[p][i]; } } if(na[p] && a+b+fa[p][0]<=x) a+=fa[p][0]; } int main() { long long x; scanf("%d", &n); for(int i=1;i<=n;i++) scanf("%d",&d[i].v); for(int i=1;i<=n;i++) d[i].i=i; sort(d+1,d+n+1,cmp); for(int i=1;i<=n;i++) p[d[i].i]=i; for(int i=1;i<=n;i++) d[i].l=i-1,d[i].r=i+1; d[1].l=d[n].r=0; for(int i=1;i<=n;i++) { j=p[i];l=d[j].l;r=d[j].r; if(dir()) nb[i]=d[l].i,na[i]=pd(d[l].l,r); else nb[i]=d[r].i,na[i]=pd(l,d[r].r); if(l) d[l].r=r; if(r) d[r].l=l; } for(int i=1;i<=n;i++) { f[i][0]=nb[na[i]]; fa[i][0]=abs(d[p[i]].v-d[p[na[i]]].v); fb[i][0]=abs(d[p[f[i][0]]].v-d[p[na[i]]].v); } st(); scanf("%lld%d",&x,&m); for(int i=1;i<=n;i++) { get(x,i); if(b && ((double)a)/((double)b)<minn) { minn=((double)a)/((double)b); ans=i; } } printf("%d\n",ans); for(int i=1;i<=m;i++) { scanf("%d%lld",&j,&x); get(x,j); printf("%d %d\n",a,b); } return 0; } ```