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

2024-01-10 18:04

本文主要是介绍NOIP2012提高组day1-T3:开车旅行,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

[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=hihj

旅行过程中,小 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 109hi109 1 ≤ s i ≤ n 1 \le s_i \le n 1sin 0 ≤ x i ≤ 1 0 9 0 \le x_i \le 10^9 0xi109
数据保证 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(1k,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,i1)
    • 第二部分,由于 i > 1 i>1 i>1 2 i − 1 2^{i-1} 2i1是偶数,不换人,还有由小 A \text{A} A先驾驶从 f ( 0 , s , i − 1 ) f(0,s,i-1) f(0,s,i1),行驶到 f ( 0 , f ( 0 , s , i − 1 ) , i − 1 ) f(0,f(0,s,i-1),i-1) f(0,f(0,s,i1),i1)
    • 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,i1),i1)

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(1k,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(1k,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(1k,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,i1)+da(k,f(k,s,i1),i1)
    • 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,i1)+db(1k,f(k,s,i1),i1)

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

时间复杂度

  • 预处理 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^if[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 --){//如果能够到达城市,并且总距离不超过xif(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;
}

这篇关于NOIP2012提高组day1-T3:开车旅行的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/591619

相关文章

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

如何提高开发的效率,让老板不知所措的给你发工资

设计模式 UML JSP 编程 数据结构 1.你可能会常常发现,写了一段代码后,编译程序时是一大堆的出错 (原因:语法不熟)  ──别担心,这是每个程序员必须经历的事,这时候你就需要更大的耐心及细心,对每一行代码进行仔细人阅读并改正,这个很重要,这可以培养你的理解代码能力,所以要常读程序,不要等到程序运行以后才知道你的程序的结果。  ──如何避免:在写代码以前,要认真的学习计算机语

Java开发实例大全提高篇——Applet的应用

开发十年,就只剩下这套架构体系了! >>>    第21章  Applet的应用 21.1  Applet在html中的使用 实例549  在html中显示Applet HtmlShowApplet.java     public void paint(Graphics g){         g.drawString("html文件已经运行", 50, 50);// 绘制文本

Java开发实例大全提高篇——Java安全

开发十年,就只剩下这套架构体系了! >>>    第6篇  Java安全与Applet应用篇 第20章  Java安全 20.1  Java对称加密 实例531  使用BASE64加密     public static String encryptBASE64(byte[] data) {         //加密数据         return (new BASE64Encoder()

2024国赛论文拿奖快对照这几点及评阅要点,勿踩雷区!(国赛最后冲刺,提高获奖概率)

↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 2024“高教社杯”全国大学生数学建模竞赛已过去第三个夜晚,小伙伴们都累了没有,如果感到思维滞涩,别忘了稍作休息,放松一下自己,准备迎接国赛非常重要的收尾阶段——论文。 国赛这几天的努力最后都

C++提高编程三(vector容器、deque容器)

文章目录 vector容器vector赋值操作vector容量和大小vector插入和删除vector数据存取vector互换容器vector预留空间deque容器构造函数deque赋值操作deque大小操作deque 插入和删除deque 数据存取deque 排序 vector容器 vector容器数据结构和数组相似,也称为单端数组。区别在于数组是静态空间,vector可以

随着人们网络安全意识提高,软件架构设计与评估也成为重中之重

目录 案例 【题目】 【问题 1】(13 分) 【问题 2】(12分) 【答案】 【问题 1】答案 【问题 2】答案 相关推荐 案例         阅读以下关于软件架构设计与评估的叙述,回答问题 1 和问题 2。 【题目】         某电子商务公司为正更好地管理用户,提升企业销售业绩,拟开发一套用户管理系统。该系统的基本功能是根据用户的消费级别、消费历史、信

兔子-提高xampp中php的版本/提高php项目的版本

我是一个php菜鸟,我的博客也不是多么高大上,我只是记录下我自学过程中遇到的问题,有待于以后在复习,同时也希望能帮助到大家。 我用的开发环境是:xampp+phpstorm 解决办法:安装一个带有高版本php的xampp 以下是我出现这个问题到解决问题的过程。 曾经我在这里改php的版本,但是echo phpversion();版本总是不变。 后来经过问别人,别人建议我