#P1081. [NOIP2012 提高组] 开车旅行

[NOIP2012 提高组] 开车旅行

题目描述

A\text{A} 和小 B\text{B} 决定利用假期外出旅行,他们将想去的城市从 11 nn 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 ii 的海拔高度为hih_i,城市 ii 和城市 jj 之间的距离 di,jd_{i,j} 恰好是这两个城市海拔高度之差的绝对值,即 di,j=hihjd_{i,j}=|h_i-h_j|

旅行过程中,小 A\text{A} 和小 B\text{B} 轮流开车,第一天小 A\text{A} 开车,之后每天轮换一次。他们计划选择一个城市 ss 作为起点,一直向东行驶,并且最多行驶 xx 公里就结束旅行。

A\text{A} 和小 B\text{B} 的驾驶风格不同,小 B\text{B} 总是沿着前进方向选择一个最近的城市作为目的地,而小 A\text{A} 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 xx 公里,他们就会结束旅行。

在启程之前,小 A\text{A} 想知道两个问题:

1、 对于一个给定的 x=x0x=x_0,从哪一个城市出发,小 A\text{A} 开车行驶的路程总数与小 B\text{B} 行驶的路程总数的比值最小(如果小 B\text{B} 的行驶路程为 00,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 A\text{A} 开车行驶的路程总数与小 B\text{B} 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。

2、对任意给定的 x=xix=x_i 和出发城市 sis_i,小 A\text{A} 开车行驶的路程总数以及小 B\text B 行驶的路程总数。

输入格式

第一行包含一个整数 nn,表示城市的数目。

第二行有 nn 个整数,每两个整数之间用一个空格隔开,依次表示城市 11 到城市 nn 的海拔高度,即 h1,h2...hnh_1,h_2 ... h_n,且每个 hih_i 都是互不相同的。

第三行包含一个整数 x0x_0

第四行为一个整数 mm,表示给定 mmsis_ixix_i

接下来的 mm 行,每行包含 22 个整数 sis_ixix_i,表示从城市sis_i 出发,最多行驶 xix_i 公里。

输出格式

输出共 m+1m+1 行。

第一行包含一个整数 s0s_0,表示对于给定的 x0x_0,从编号为 s0s_0 的城市出发,小 A\text A 开车行驶的路程总数与小 B\text B 行驶的路程总数的比值最小。

接下来的 mm 行,每行包含 22 个整数,之间用一个空格隔开,依次表示在给定的 sis_ixix_i 下小 A\text A 行驶的里程总数和小 B\text B 行驶的里程总数。

4 
2 3 1 4 
3 
4 
1 3 
2 3 
3 3 
4 3

1 
1 1 
2 0 
0 0 
0 0 
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 
3 2 
2 4 
2 1 
2 4 
5 1 
5 1 
2 1 
2 0 
0 0 
0 0

提示

【样例1说明】

各个城市的海拔高度以及两个城市间的距离如上图所示。

如果从城市 11 出发,可以到达的城市为 2,3,42,3,4,这几个城市与城市 11 的距离分别为 1,1,21,1,2,但是由于城市 33 的海拔高度低于城市 22,所以我们认为城市 33 离城市 11 最近,城市 22 离城市 11 第二近,所以小A会走到城市 22。到达城市 22 后,前面可以到达的城市为 3,43,4,这两个城市与城市 22 的距离分别为 2,12,1,所以城市 44 离城市 22 最近,因此小B会走到城市44。到达城市 44 后,前面已没有可到达的城市,所以旅行结束。

如果从城市 22 出发,可以到达的城市为 3,43,4,这两个城市与城市 22 的距离分别为 2,12,1,由于城市 33 离城市 22 第二近,所以小 A\text A 会走到城市 33。到达城市 33 后,前面尚未旅行的城市为 44,所以城市 44 离城市 33 最近,但是如果要到达城市 44,则总路程为 2+3=5>32+3=5>3,所以小 B\text B 会直接在城市 33 结束旅行。

如果从城市 33 出发,可以到达的城市为 44,由于没有离城市 33 第二近的城市,因此旅行还未开始就结束了。

如果从城市 44 出发,没有可以到达的城市,因此旅行还未开始就结束了。

【样例2说明】

x=7x=7 时,如果从城市 11 出发,则路线为 123891 \to 2 \to 3 \to 8 \to 9,小 A\text A 走的距离为 1+2=31+2=3,小 B\text B 走的距离为 1+1=21+1=2。(在城市 11 时,距离小 A\text A 最近的城市是 2266,但是城市 22 的海拔更高,视为与城市 11 第二近的城市,所以小 A\text A 最终选择城市 22;走到99 后,小 A\text A 只有城市 1010 可以走,没有第二选择可以选,所以没法做出选择,结束旅行)

如果从城市 22 出发,则路线为 2672 \to 6 \to 7,小 A\text A 和小 B\text B 走的距离分别为 2,42,4

如果从城市 33 出发,则路线为 3893 \to 8 \to 9,小 A\text A 和小 B\text B 走的距离分别为2,12,1

如果从城市 44 出发,则路线为 4674 \to 6 \to 7,小 A\text A 和小 B\text B 走的距离分别为 2,42,4

如果从城市 55 出发,则路线为 5785 \to 7 \to 8,小 A\text A 和小 B\text B 走的距离分别为 5,15,1

如果从城市 66 出发,则路线为 6896 \to 8 \to 9,小 A\text A 和小 B\text B 走的距离分别为5,15,1

如果从城市 77 出发,则路线为 79107 \to 9 \to 10,小 A\text A 和小 B\text B 走的距离分别为2,12,1

如果从城市 88 出发,则路线为 8108 \to 10,小 A\text A 和小 B\text B 走的距离分别为2,02,0

如果从城市 99 出发,则路线为 99,小 A\text A 和小 B\text B 走的距离分别为 0,00,0(旅行一开始就结束了)。

如果从城市 1010 出发,则路线为 1010,小 A\text A 和小 B\text B 走的距离分别为0,00,0

从城市 22 或者城市 44 出发小 A\text A 行驶的路程总数与小 B\text B 行驶的路程总数的比值都最小,但是城市 22 的海拔更高,所以输出第一行为 22

【数据范围与约定】

对于 30%30\% 的数据,有1n20,1m201\le n \le 20,1\le m\le 20
对于40%40\% 的数据,有1n100,1m1001\le n \le 100,1\le m\le 100
对于 50%50\% 的数据,有1n100,1m10001\le n \le 100,1\le m\le 1000
对于 70%70\% 的数据,有1n1000,1m1041\le n \le 1000,1\le m\le 10^4
对于 100%100\% 的数据:1n,m1051\le n,m \le 10^5109hi109-10^9 \le h_i≤10^91sin1 \le s_i \le n0xi1090 \le x_i \le 10^9
数据保证 hih_i 互不相同。