题意:
两个人爬山,时刻要保证在同一水平面上,直到两人互换位置。问走过的最短距离。两点间距离定义为两点间的y轴绝对值差。
给力条件:除了首尾两点每个点的y坐标均不相同
解法:
DP?杀鸡用牛刀,没必要!
贪心!
首先明确,不能走回头路,这里的回头路指完全退回到上个步骤所在的点,显然,这样的走法是无意义的。
设置两个指针,p1指向头,p2指向尾,循环至两个指针重叠。下面具体分四种情况讨论:
1、如果y
p1+1>y
p1且y
p2-1>y
p2,这种情况下当然山峰高的帮助山峰低的越过低的山峰
2、如果y
p1+1>y
p1且y
p2-1<y
p2,这种情况又要分两种情况:
2.1 如果(p1,p1+1)这段上坡通过局部回退能够让p2度过这个山谷,显然这样就是p2--
2.2 否则p1必须回退至上个拐点,试图获得更低的高度,这样就是p1--
3、如果y
p1+1<y
p1且y
p2-1>y
p2,与上种情况类似,不加赘述。
4、如果y
p1+1<y
p1且y
p2-1<y
p2,这种情况不应该是正常情况下应该出现的,因该是碰到某个很深的山谷后上坡段回退形成的,这时候应该继续后退,以寻求更低点。
代码里写的很清楚,大家看代码吧:
1# include <cstdio>
2using namespace std;
3# define min(a,b) ((a)<(b)?(a):(b))
4# define max(a,b) ((a)>(b)?(a):(b))
5int p[1001][2],n,p1,p2,ans,last;
6int main()
7{
8 int test;
9 scanf("%d",&test);
10 while(test--)
11 {
12 scanf("%d",&n);
13 for(int i=0;i<n;i++)
14 scanf("%d %d",&p[i][0],&p[i][1]);
15 p1=0,p2=n-1,ans=0;
16 last=p[0][1];
17 while(p2>p1)
18 {
19 if(p[p2-1][1]>p[p2][1]&&p[p1+1][1]>p[p1][1])
20 {
21 ans+=2*(min(p[p2-1][1],p[p1+1][1])-last);
22 last=min(p[p2-1][1],p[p1+1][1]);
23 if(p[p2-1][1]==last) p2--;
24 if(p[p1+1][1]==last) p1++;
25 }
26 else if(p[p2-1][1]<p[p2][1]&&p[p1+1][1]>p[p1][1])
27 {
28 ans+=2*(last-max(p[p2-1][1],p[p1][1]));
29 last=max(p[p2-1][1],p[p1][1]);
30 if(last==p[p2-1][1]) p2--;
31 else p1--;
32 }
33 else if(p[p2-1][1]>p[p2][1]&&p[p1+1][1]<p[p1][1])
34 {
35 ans+=2*(last-max(p[p2][1],p[p1+1][1]));
36 last=max(p[p2][1],p[p1+1][1]);
37 if(last==p[p1+1][1]) p1++;
38 else p2++;
39 }
40 else
41 {
42 ans+=2*(min(p[p1][1],p[p2][1])-last);
43 last=min(p[p1][1],p[p2][1]);
44 if(last==p[p1][1]) p1--;
45 else p2++;
46 }
47 }
48 printf("%d\n",ans*2);
49 }
50 return 0;
51}
52