NOIP2012提高组day1-T3:开车旅行

发布时间:2024年01月10日

题目链接

[NOIP2012 提高组] 开车旅行

题目描述

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

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

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

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

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

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

输入格式

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

第二行有 n n n 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 1 1 到城市 n n n 的海拔高度,即 h 1 , h 2 . . . h n h_1,h_2 ... h_n h1?,h2?...hn?,且每个 h i h_i hi? 都是互不相同的。

第三行包含一个整数 x 0 x_0 x0?

第四行为一个整数 m m m,表示给定 m m m s i s_i si? x i x_i xi?

接下来的 m m m 行,每行包含 2 2 2 个整数 s i s_i si? x i x_i xi?,表示从城市 s i s_i si? 出发,最多行驶 x i x_i xi? 公里。

输出格式

输出共 m + 1 m+1 m+1 行。

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

接下来的 m m m 行,每行包含 2 2 2 个整数,之间用一个空格隔开,依次表示在给定的 s i s_i si? x i x_i xi? 下小 A \text A A 行驶的里程总数和小 B \text B B 行驶的里程总数。

样例 #1

样例输入 #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

样例输入 #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

提示

【样例1说明】

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

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

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

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

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

【样例2说明】

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

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

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

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

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

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

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

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

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

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

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

【数据范围与约定】

对于 30 % 30\% 30% 的数据,有 1 ≤ n ≤ 20 , 1 ≤ m ≤ 20 1\le n \le 20,1\le m\le 20 1n20,1m20
对于 40 % 40\% 40% 的数据,有 1 ≤ n ≤ 100 , 1 ≤ m ≤ 100 1\le n \le 100,1\le m\le 100 1n100,1m100
对于 50 % 50\% 50% 的数据,有 1 ≤ n ≤ 100 , 1 ≤ m ≤ 1000 1\le n \le 100,1\le m\le 1000 1n100,1m1000
对于 70 % 70\% 70% 的数据,有 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 1 0 4 1\le n \le 1000,1\le m\le 10^4 1n1000,1m104
对于 100 % 100\% 100% 的数据: 1 ≤ n , m ≤ 1 0 5 1\le n,m \le 10^5 1n,m105 ? 1 0 9 ≤ h i ≤ 1 0 9 -10^9 \le h_i≤10^9 ?109hi?109 1 ≤ s i ≤ n 1 \le s_i \le n 1si?n 0 ≤ x i ≤ 1 0 9 0 \le x_i \le 10^9 0xi?109
数据保证 h i h_i hi? 互不相同。

算法思想

根据题目描述,本题要求的是选择一个城市 s s s 作为起点,一直向东行驶,并且最多行驶 x x x 公里就结束旅行时,小 A \text{A} A 开车行驶的路程总数以及小 B \text B B 行驶的路程总数。

由于小 A \text{A} A和小 B \text{B} B一直向东行驶,并且最多行驶 x x x 公里就结束旅行,可以使用倍增法统计出小 A \text{A} A 和小 B \text B B 开车行驶的路程总数 l a la la l b lb lb

状态表示

  • d a ( 0 , s , i ) da(0,s,i) da(0,s,i)表示从城市 s s s出发,小 A \text{A} A先走,两人轮流行驶了 2 i 2^i 2i次,小 A \text{A} A行驶的总距离。
  • d a ( 1 , s , i ) da(1,s,i) da(1,s,i)表示从城市 s s s出发,小 B \text{B} B先走,两人轮流行驶了 2 i 2^i 2i次,小 A \text{A} A行驶的总距离。
  • d b ( 0 , s , i ) db(0,s,i) db(0,s,i)表示从城市 s s s出发,小 A \text{A} A先走,两人轮流行驶了 2 i 2^i 2i次,小 B \text{B} B行驶的总距离。
  • d b ( 1 , s , i ) db(1,s,i) db(1,s,i)表示从城市 s s s出发,小 B \text{B} B先走,两人轮流行驶了 2 i 2^i 2i次,小 B \text{B} B行驶的总距离。

有了上述状态,如何求从 s s s 出发,最多行驶 x x x 公里时的 l a la la l b lb lb呢?不妨设两人轮流行驶了 k k k次,以二进制的方式分析,假设 k = ( 011010010 ) 2 k=(011010010)_2 k=(011010010)2?,那么
l a = d a ( 0 , s , 7 ) + d a ( 0 , s 1 , 6 ) + d a ( 0 , s 2 , 4 ) + d a ( 0 , s 3 , 1 ) l b = d b ( 0 , s , 7 ) + d b ( 0 , s 1 , 6 ) + d b ( 0 , s 2 , 4 ) + d b ( 0 , s 3 , 1 ) la = da(0,s,7)+da(0,s_1,6)+da(0,s_2,4)+da(0,s_3,1)\\ lb = db(0,s,7)+db(0,s_1,6)+db(0,s_2,4)+db(0,s_3,1) la=da(0,s,7)+da(0,s1?,6)+da(0,s2?,4)+da(0,s3?,1)lb=db(0,s,7)+db(0,s1?,6)+db(0,s2?,4)+db(0,s3?,1)

其中 s 1 , s 2 , s 3 . . . s_1,s_2,s_3... s1?,s2?,s3?...为中间经过的城市。要求解中间经过的城市,还需要预处理

  • f ( 0 , s , i ) f(0,s,i) f(0,s,i)表示从城市 s s s出发,小 A \text{A} A先走,两人轮流行驶了 2 i 2^i 2i次到达的城市编号
  • f ( 1 , s , i ) f(1,s,i) f(1,s,i)表示从城市 s s s出发,小 B \text{B} B先走,两人轮流行驶了 2 i 2^i 2i次到达的城市编号

由于题目要求,小 A \text{A} A和小 B \text{B} B的驾驶风格不同。因此,还需要预处理出:

  • g a ( i ) ga(i) ga(i)表示小 A \text{A} A从城市 s s s出发能够到达的城市编号
  • g b ( i ) gb(i) gb(i)表示小 B \text{B} B从城市 s s s出发能够到达的城市编号

下面再来考虑一些如何计算上述状态

状态计算

1、 先来看一下如何计算 g a ga ga g b gb gb

  • 由于小 A \text{A} A总是沿着前进方向选择第二近的城市作为目的地,那么就是求城市 s s s右边和它的海拔高度之差第 2 2 2小的城市
  • B \text{B} B 总是沿着前进方向选择一个最近的城市作为目的地,那么就是求城市 s s s右边和它的海拔高度之差最小的城市

即在 s s s右侧的城市中,查找与 s s s高度之差的绝对值最小的两个城市,其原理类似于博主的这篇文章——邻值查找

为了快速查找目标,可以使用set作为容器,从后向前遍历每个城市:

  • 查找第 1 1 1个高度大于 h [ s ] h[s] h[s]的城市和第 2 2 2个高度大于 h [ s ] h[s] h[s]的城市
  • 查找第 1 1 1个高度小于 h [ s ] h[s] h[s]的城市和第 2 2 2个高度小于 h [ s ] h[s] h[s]的城市
  • 那么,目标就在这 4 4 4个城市之间,如下图所示。
  • 再将城市 s s s插入到set中。
    在这里插入图片描述

2、再看如何计算 f ( 0 , s , i ) f(0,s,i) f(0,s,i) f ( 0 , s , i ) f(0,s,i) f(0,s,i)

  • i = 0 i=0 i=0时,表示从 s s s出发行驶 1 1 1次,那么 f ( 0 , s , 0 ) = g a ( s ) f(0,s,0) = ga(s) f(0,s,0)=ga(s) f ( 1 , s , 0 ) = g b ( s ) f(1,s,0) = gb(s) f(1,s,0)=gb(s)
  • i = 1 i=1 i=1时,表示从 s s s出发行驶 2 2 2
    • 1 1 1次小 A \text{A} A先驾驶从 s s s行驶到 f ( 0 , s , 0 ) f(0,s,0) f(0,s,0)
    • 2 2 2次换小 B \text{B} B驾驶从 f ( 0 , s , 0 ) f(0,s,0) f(0,s,0)行驶到了 f ( 1 , f ( 0 , s , 0 ) , 0 ) f(1,f(0,s,0),0) f(1,f(0,s,0),0)
    • k k k表示由谁先驾驶, k = 0 k=0 k=0表示小 A \text{A} A先驾驶, k = 1 k=1 k=1表示小 B \text{B} B先驾驶,那么 f ( k , s , 1 ) = f ( 1 ? k , f ( k , s , 0 ) , 0 ) f(k,s,1)=f(1-k,f(k,s,0),0) f(k,s,1)=f(1?k,f(k,s,0),0)
  • i > 1 i>1 i>1时,表示从 s s s出发行驶 2 i 2^i 2i次,也可以分成两部分
    • 第一部分, 小 A \text{A} A先驾驶从 s s s行驶到 f ( 0 , s , i ? 1 ) f(0,s,i-1) f(0,s,i?1)
    • 第二部分,由于 i > 1 i>1 i>1 2 i ? 1 2^{i-1} 2i?1是偶数,不换人,还有由小 A \text{A} A先驾驶从 f ( 0 , s , i ? 1 ) f(0,s,i-1) f(0,s,i?1),行驶到 f ( 0 , f ( 0 , s , i ? 1 ) , i ? 1 ) f(0,f(0,s,i-1),i-1) f(0,f(0,s,i?1),i?1)
    • f ( k , s , i ) = f ( k , f ( k , s , i ? 1 ) , i ? 1 ) f(k,s,i)=f(k,f(k,s,i-1),i-1) f(k,s,i)=f(k,f(k,s,i?1),i?1)

3、最后再计算 d a da da d b db db

  • i = 0 i=0 i=0时,即行驶 1 1 1

    • d a ( 0 , s , 0 ) da(0,s,0) da(0,s,0)表示小 A \text{A} A先走,行驶 1 1 1次,会从城市 s s s到达 g a ( s ) ga(s) ga(s),那么 d a ( 0 , s , 0 ) = d i s t ( s , g a ( s ) ) da(0,s,0)=dist(s, ga(s)) da(0,s,0)=dist(s,ga(s)),即这两个城市海拔高度之差的绝对值;如果小 B \text{B} B先走,那么小 A \text{A} A行驶的距离为 0 0 0,即 d a ( 1 , s , 0 ) = 0 da(1,s,0)=0 da(1,s,0)=0
    • 同理, d b ( 1 , s , 0 ) = d i s t ( s , g b ( s ) ) db(1,s,0)=dist(s, gb(s)) db(1,s,0)=dist(s,gb(s)) d b ( 0 , s , 0 ) = 0 db(0,s,0)=0 db(0,s,0)=0
  • i = 1 i=1 i=1时,即行驶 2 2 2次,可以分成两部分,不妨用 k k k表示谁先行驶, k = { 0 , 1 } k=\{0,1\} k={0,1}

    • 第一部分从 s s s出发,行驶 1 1 1次,走到 f ( k , s , 0 ) f(k,s,0) f(k,s,0),小 A \text{A} A行驶的距离 d a ( k , s , 0 ) da(k,s,0) da(k,s,0)
      B \text{B} B行驶的距离为 d b ( k , s , 0 ) db(k,s,0) db(k,s,0)
    • 第二部分从 f ( k , s , 0 ) f(k,s,0) f(k,s,0)出发,换人行驶 1 1 1次,小 A \text{A} A行驶的距离 d a ( 1 ? k , f ( k , s , 0 ) , 0 ) da(1-k,f(k,s,0),0) da(1?k,f(k,s,0),0)
      B \text{B} B行驶的距离为 d b ( k , f ( k , s , 0 ) , 0 ) db(k,f(k,s,0),0) db(k,f(k,s,0),0)
    • 那么, d a ( k , s , 1 ) = d a ( k , s , 0 ) + d a ( 1 ? k , f ( k , s , 0 ) , 0 ) da(k,s,1)=da(k,s,0)+da(1-k,f(k,s,0),0) da(k,s,1)=da(k,s,0)+da(1?k,f(k,s,0),0) d b ( k , s , 1 ) = d b ( k , s , 0 ) + d b ( 1 ? k , f ( k , s , 0 ) , 0 ) db(k,s,1)=db(k,s,0)+db(1-k,f(k,s,0),0) db(k,s,1)=db(k,s,0)+db(1?k,f(k,s,0),0)
  • i > 1 i>1 i>1时,即行驶 2 i 2^i 2i次,也可以分成两部分, k k k表示谁先行驶, k = { 0 , 1 } k=\{0,1\} k={0,1}

    • d a ( k , s , i ) = d a ( k , s , i ? 1 ) + d a ( k , f ( k , s , i ? 1 ) , i ? 1 ) da(k,s,i)=da(k,s,i-1)+da(k,f(k,s,i-1),i-1) da(k,s,i)=da(k,s,i?1)+da(k,f(k,s,i?1),i?1)
    • d b ( k , s , i ) = d b ( k , s , i ? 1 ) + d b ( 1 ? k , f ( k , s , i ? 1 ) , i ? 1 ) db(k,s,i)=db(k,s,i-1)+db(1-k,f(k,s,i-1),i-1) db(k,s,i)=db(k,s,i?1)+db(1?k,f(k,s,i?1),i?1)

如下图所示
在这里插入图片描述

时间复杂度

  • 预处理 g a , g b ga,gb ga,gb需要从后向前遍历每个城市 s s s,查找与 s s s高度之差的绝对值最小的两个城市,使用set容器查找的时间复杂度为 O ( l o g n ) O(logn) O(logn),总的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
  • 通过倍增法预处理 f f f的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
  • 通过倍增法预处理 d a , d b da,db da,db的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
  • 第一问求对于给定的 x x x,从哪个城市出发,小 A \text A A 开车行驶的路程总数与小 B \text B B 行驶的路程总数的比值最小,需要枚举每个城市作为起点,求 l a la la l b lb lb,时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
  • 第二问一共有 m m m个询问,求在给定的 s s s x x x 情况下求小 A \text A A 行驶的里程总数和小 B \text B B 行驶的里程总数,时间复杂度为 O ( m l o g n ) O(mlogn) O(mlogn)

总的时间复杂度为 O ( n l o g n ) = 1 0 5 × 17 O(nlogn)=10^5\times17 O(nlogn)=105×17

代码实现

#include <iostream>
#include <set>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 1e5 + 10, M = 17;
const LL INF = 1e18; 
int n, h[N];
int ga[N], gb[N]; //ga[i]表示小A从i出发能到达的城市
int f[2][N][M]; //f[0][s][i]表示从s出发,小A先走,轮流行驶2^i时到达的城市编号
int da[2][N][M], db[2][N][M];
void init_g()
{
    set<PLI> S;
    //防止查找越界,插入4个边界
    S.insert({-INF, 0}), S.insert({-INF + 1, 0});
    S.insert({INF, 0}), S.insert({INF + 1, 0});
    PLI b[4]; //被选城市
    //从后向前遍历城市,查找右侧第一个大于h[i]的位置
    for(int i = n; i >= 0; i --)
    {
        PLI t(h[i], i);
        auto it = S.upper_bound(t);
        it ++; //移动到右侧第二个大于h[i]的位置
        for(int k = 0; k < 4; k ++) b[k] = *it --;
        //从备选的4个备选城市中查找差值第1小和第2小的城市
        LL d1 = INF, d2 = INF;
        int p1, p2;
        for(int k = 3; k >= 0; k --)
        {
            LL d = abs(h[i] - b[k].first);
            if(d < d1) {
                d2 = d1, d1 = d;
                p2 = p1, p1 = b[k].second; 
            }
            else if(d < d2) {
                d2 = d, p2 = b[k].second;
            }
        }
        //小A选择第二近的城市作为目的地,小B选择一个最近的城市作为目的地,
        ga[i] = p2, gb[i] = p1;
        S.insert(t);
    }
}
void init_f()
{
    //初始状态,从每个城市出发行驶1次能到达的城市
    for(int s = 1; s <= n; s ++) 
    {
        f[0][s][0] = ga[s], f[1][s][0] = gb[s];
    }
    //状态计算
    for(int i = 1; i < M; i ++)
        for(int s = 1; s <= n; s ++)
            for(int k = 0; k < 2; k ++)
            {
                if(i == 1) //行驶2次
                    f[k][s][i] = f[1 - k][f[k][s][0]][0];
                else //行驶2^i
                    f[k][s][i] = f[k][f[k][s][i - 1]][i - 1];
            }
}
//获取两个城市之间的距离
int get_dis(int a, int b)
{
    return abs(h[a] - h[b]);
}
void init_d()
{
    //初始状态,计算从每个城市出发行驶1次能够走的额距离
    for(int s = 1; s <= n; s ++)
    {
        da[0][s][0] = get_dis(s, ga[s]);
        db[1][s][0] = get_dis(s, gb[s]);
    }
    //状态计算
    for(int i = 1; i < M; i ++)
        for(int s = 1; s <= n; s ++)
            for(int k = 0; k < 2; k ++)
            {
                if(i == 1) //行驶2次
                {
                    da[k][s][i] = da[k][s][i - 1] + da[1 - k][f[k][s][i - 1]][i - 1];
                    db[k][s][i] = db[k][s][i - 1] + db[1 - k][f[k][s][i - 1]][i - 1];
                }
                else //行驶2^i次
                {
                    da[k][s][i] = da[k][s][i - 1] + da[k][f[k][s][i - 1]][i - 1];
                    db[k][s][i] = db[k][s][i - 1] + db[k][f[k][s][i - 1]][i - 1];
                }
            }
}
//计算从城市s出发,行驶总距离不超过s时,小A和小B各自走的总距离
void work(int s, int x, int &la, int &lb)
{
    la = lb = 0;
    //枚举行驶次数
    for(int i = M - 1; i >= 0; i --)
    {
        //如果能够到达城市,并且总距离不超过x
        if(f[0][s][i] && la + lb + da[0][s][i] + db[0][s][i] <= x)
        {
            la += da[0][s][i], lb += db[0][s][i];
            s = f[0][s][i];//行驶到新的城市s
        }
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    //预处理状态
    init_g();
    init_f();
    init_d();
    //第一问
    int x;
    scanf("%d", &x);
    int ans = 0, max_h = 0;
    double min_r = INF;
    for(int s = 1; s <= n; s ++)
    {
        int la, lb;
        work(s, x, la, lb);
        double r = lb == 0 ? INF : (double) la / lb;
        //取最小比值,比值相同取海拔更高的城市
        if(r < min_r || r == min_r && h[s] > max_h)
        {
            min_r = r, max_h = h[s], ans = s;
        }
    }
    printf("%d\n", ans);
    //第二问
    int m;
    scanf("%d", &m);
    while (m -- )
    {
        int s, x, la, lb;
        scanf("%d%d", &s, &x);
        work(s, x, la, lb);
        printf("%d %d\n", la, lb);
    }
    return 0;
}

文章来源:https://blog.csdn.net/qiaoxinwei/article/details/135497751
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。