題目描述

輸入輸出格式

輸入輸出樣例

輸入樣例#1：
4
2 3 1 4
3
4
1 3
2 3
3 3
4 3
輸出樣例#1：
1
1 1
2 0
0 0
0 0

輸入樣例#2：
10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7
輸出樣例#2：
2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std;inline long long read(){long long s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return (long long)s*w; }int main() {double num=1000000000,jd=1e-8;long long n,ans,m,k,x,x0,h[1000010],x1[1000010],x2[1000010],dis1[1000010],dis2[1000010];n=read();for (int i=1;i<=n;i++) h[i]=read();for (int i=n-1;i>=1;i--){int mn1=i+1,mn2=0; dis1[i]=abs(h[i]-h[mn1]);for (int j=i+2;j<=n;j++)if (dis1[i]>abs(h[i]-h[j])||(dis1[i]==abs(h[i]-h[j])&&h[j]<h[mn1])) {dis2[i]=dis1[i];dis1[i]=abs(h[i]-h[j]);mn2=mn1;mn1=j;} elseif (dis2[i]==0||dis2[i]>abs(h[i]-h[j])||(dis2[i]==abs(h[i]-h[j])&&h[j]<h[mn2])){dis2[i]=abs(h[i]-h[j]);mn2=j;}x1[i]=mn1;x2[i]=mn2;}x0=read();ans=0;for (int i=1;i<=n;i++){int d1=0,d2=0,d=0,k=i;while (1){if (d){if (d1+d2+dis1[k]>x0||!x1[k]) break;d2+=dis1[k];k=x1[k];} else{if (d1+d2+dis2[k]>x0||!x2[k]) break;d1+=dis2[k];k=x2[k];}d^=1;}if (!ans||1.0*d1/d2-num<-jd||fabs(1.0*d1/d2-num)<=jd&&h[ans]<h[i]){num=1.0*d1/d2;ans=i;}}printf("%lld\n",ans);m=read();while (m--){k=read();x=read();int d1=0,d2=0,d=0;while (1){if (d!=0){if (d1+d2+dis1[k]>x||!x1[k]) break;d2+=dis1[k];k=x1[k];} else{if (d1+d2+dis2[k]>x||!x2[k]) break;d1+=dis2[k];k=x2[k];}d^=1;}printf("%lld %lld\n",d1,d2);}return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/10458925.html

總結

以上是生活随笔為你收集整理的开车旅行(70分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。