https://www.luogu.org/problem/show?pid=1081
太遗憾了明明写出来了，却把最小值初始值弄小了，从第二个点开始就不可能对了。70分!
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int n,x0,m; long long h[1000009]; int f[2][1000009]; double mint1=1e9+9.1,INF=1e9+9.1; int mint1w=1; int now,H=0; void work(int x,long long tot,int id,long long a,long long b)//当前起点，剩余路程 { if(tot==0||x==n) { if(!b) return ; if(mint1>1.000*a/b) mint1=1.000*a/b,mint1w=now,H=h[now]; if(mint1==1.00*a/b&&h[now]>H) mint1w=now,H=h[now]; return ; } int t=f[id][x]; if(abs(h[t]-h[x]) <=tot) if(id) work(t,tot-abs(h[t]-h[x]),!id,a+abs(h[t]-h[x]),b); else work(t,tot-abs(h[t]-h[x]),!id,a,b+abs(h[t]-h[x])); else { if(!b) return ; if(mint1>1.000*a/b) mint1=1.000*a/b,mint1w=now,H=h[now]; if(mint1==1.00*a/b &&h[now]>H) mint1w=now,H=h[now]; return ; } return; } void find(int x,long long tot,int id,long long a,long long b) { if(tot==0||x==n) { printf("%lld %lld ",a,b); return ; } int t=f[id][x]; if(abs(h[t]-h[x])<=tot) if(id) find(t,tot-abs(h[t]-h[x]),!id,a+abs(h[t]-h[x]),b); else find(t,tot-abs(h[t]-h[x]),!id,a,b+abs(h[t]-h[x])); else { printf("%lld %lld ",a,b); return ; } } int main() { scanf("%d",&n); long long MM=-INF,MW=1; for(int i=1;i<=n;i++) { scanf("%lld",&h[i]); if(h[i]>MM) MM=h[i],MW=i; } h[n+1]=1e15+9; scanf("%d",&x0); double min1,min2,minw1,minw2,t; for(int i=1;i<=n;i++) { min1=INF,min2=INF,minw1=n+1,minw2=n+1,t; for(int j=i+1;j<=n;j++) { t=abs(h[j]-h[i]); if(h[j]>h[i]) t+=0.1; if(h[j]<h[i]) t-=0.1; if(t<min1) { min2=min1,minw2=minw1; min1=t,minw1=j; }else if(t<min2) min2=t,minw2=j; } f[0][i]=minw1,f[1][i]=minw2; } for(int i=1;i<=n;i++) now=i,work(i,x0,1,0,0); if(mint1==INF) printf("%d ",MW); else printf("%d ",mint1w); scanf("%d",&m); for(int i=1,S,X;i<=m;i++) { scanf("%d%d",&S,&X); find(S,X*1LL,1,0,0); } return 0; }