/*考场上写的暴力 40分钟70分*/ #include<iostream> #include<cstdio> #include<cstring> #define base 1000000000 #define maxn 100010 #define ll long long using namespace std; ll n,m,h[maxn],X,A[maxn],B[maxn],st,ans; bool falg; double mii=base; ll init() { ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } ll Abs(ll a) { return a<0?-a:a; } void Get_AB() { for(int i=1;i<=n;i++) { ll mxx,mx,mxxh,mxh,kxx=0,kx=0;mxx=mx=0x7fffffff; for(int j=i+1;j<=n;j++) { ll C=Abs(h[i]-h[j]); if(C<mxx||(C==mxx&&h[j]<mxxh)) mx=mxx,mxx=C,mxh=mxxh,mxxh=h[j],kx=kxx,kxx=j; else if((C==mxx&&h[j]>=mxxh)||C<mx||(C==mx&&h[j]<mxh)) mx=C,mxh=h[j],kx=j; } A[i]=kx;B[i]=kxx; } } void Dfs(ll now,ll who,ll As,ll Bs,ll limit,ll S) { if(falg)return;ll s1=0,s2=0;double tmp; if(!who)s1=As+Abs(h[now]-h[A[now]]),S+=Abs(h[now]-h[A[now]]); if(who)s2=Bs+Abs(h[now]-h[B[now]]),S+=Abs(h[now]-h[B[now]]); if(S>limit||(!who&&A[now]==0)||(who&&B[now]==0)) { if(!Bs)tmp=base; else tmp=double(As)/double(Bs); if(tmp<mii||(tmp==mii&&h[st]>h[ans])) ans=st,mii=tmp; falg=1;return ; } if(!who&&s1<=limit)Dfs(A[now],!who,s1,Bs,limit,S);if(falg)return; if(who&&s2<=limit)Dfs(B[now],!who,As,s2,limit,S);if(falg)return; if(!Bs)tmp=base; else tmp=double(As)/double(Bs); if(tmp<mii||(tmp==mii&&h[st]>h[ans])) ans=st,mii=tmp; falg=1;return ; } void dfs(ll now,ll who,ll As,ll Bs,ll limit,ll S) { if(falg)return;ll s1=0,s2=0; if(!who)s1=As+Abs(h[now]-h[A[now]]),S+=Abs(h[now]-h[A[now]]); if(who)s2=Bs+Abs(h[now]-h[B[now]]),S+=Abs(h[now]-h[B[now]]); if(S>limit||(!who&&A[now]==0)||(who&&B[now]==0)) { cout<<As<<" "<<Bs<<endl; falg=1;return; } if(!who&&s1<=limit)dfs(A[now],!who,s1,Bs,limit,S);if(falg)return; if(who&&s2<=limit)dfs(B[now],!who,As,s2,limit,S);if(falg)return; cout<<As<<" "<<Bs<<endl; falg=1;return; } int main() { n=init();int x,s; for(int i=1;i<=n;i++) { x=init();h[i]=x+base; } Get_AB();X=init(); for(int i=1;i<=n;i++) falg=0,st=i,Dfs(i,0,0,0,X,0); cout<<ans<<endl; m=init(); for(int i=1;i<=m;i++) { s=init();x=init(); falg=0;dfs(s,0,0,0,x,0); } return 0; }
/* 暴力的复杂度是n*n的 首先预处理每个点的最短次短距离就Tle了 这里我们借助set O n 的解决这个问题 然后对于每个询问 利用倍增 logn的实现就不超时了 */ #include<iostream> #include<cstdio> #include<cstring> #include<set> #include<cmath> #define base 100000000000//大大大大大 #define maxn 100010 #define ll long long using namespace std; ll n,m,X,A[maxn],B[maxn],As[maxn],Bs[maxn],ans; ll d[maxn][25],f[maxn][25][2]; double mii=base; struct point { ll o,hi; bool operator < (const point & a) const { return hi<a.hi; } }p[maxn]; set<point>s; set<point>::iterator pi; ll init() { ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } ll abs(ll a) { return a<0?-a:a; } void Add(point x,point y) { if(!B[x.o]) { B[x.o]=y.o; Bs[x.o]=abs(x.hi-y.hi); } else if(abs(x.hi-y.hi)<Bs[x.o]||(abs(x.hi-y.hi)==Bs[x.o]&&y.hi<p[B[x.o]].hi)) { A[x.o]=B[x.o]; As[x.o]=Bs[x.o]; B[x.o]=y.o; Bs[x.o]=abs(x.hi-y.hi); } else if(abs(x.hi-y.hi)<As[x.o]||(abs(x.hi-y.hi)==As[x.o]&&y.hi<p[A[x.o]].hi)) { A[x.o]=y.o; As[x.o]=abs(x.hi-y.hi); } else if(!A[x.o]) { A[x.o]=y.o; As[x.o]=abs(x.hi-y.hi); } return; } void Get_AB() { for(int i=n;i>=1;i--) { s.insert(p[i]); pi=s.find(p[i]); if(pi!=s.begin()) { pi--;Add(p[i],*pi); if(pi!=s.begin()) { pi--;Add(p[i],*pi);pi++; } pi++; } if((++pi)!=s.end()) { Add(p[i],*pi); if((++pi)!=s.end()) Add(p[i],*pi); pi--; } pi--; } } void Query(int st,ll limit,ll & sa,ll & sb) { for(int i=20;i>=0;i--) if(f[st][i][1]+f[st][i][0]<=limit&&d[st][i]) { sa+=f[st][i][0];sb+=f[st][i][1]; limit-=(f[st][i][1]+f[st][i][0]);st=d[st][i]; } if(A[st]&&As[st]<=limit) sa+=As[st]; } int main() { n=init(); for(int i=1;i<=n;i++) { p[i].hi=init();p[i].o=i; } Get_AB(); for(int i=1;i<=n;i++) { d[i][0]=B[A[i]]; f[i][0][0]=As[i]; f[i][0][1]=Bs[A[i]]; } for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) { d[i][j]=d[d[i][j-1]][j-1]; f[i][j][0]=f[i][j-1][0]+f[d[i][j-1]][j-1][0]; f[i][j][1]=f[i][j-1][1]+f[d[i][j-1]][j-1][1]; } X=init(); for(int i=1;i<=n;i++) { ll sa=0,sb=0;double tmp; Query(i,X,sa,sb); if(!sb)tmp=base; else tmp=double(sa)/double(sb); if(tmp<mii||(tmp==mii&&p[i].hi>p[ans].hi)) ans=i,mii=tmp; } cout<<ans<<endl; m=init();int st; for(int i=1;i<=m;i++) { st=init();X=init(); ll sa=0,sb=0; Query(st,X,sa,sb); cout<<sa<<" "<<sb<<endl; } return 0; }