首先找到Bessie位于哪两个干草堆之间,模拟Bessie跳的过程。两遍模拟,统计Bessie左、右干草堆垫高的高度。比如Bessie左边的干草堆需要垫高,她就要尽量向右跳,跳到右边无法跨越的位置为止。
如果当前左右两个干草堆Bessie都跳不出去,则无需垫高干草堆,输出0。
核心代码:
1 for(i=1;i<=n;++i) if (a[i].p>b) break; 2 l=i-1,r=i;d=a[r].p-a[l].p; 3 while(l>0&&r<=n) 4 { 5 if (a[l].s>=d&&a[r].s>=d) 6 {puts("0");return 0;} 7 if (a[r].s<d) 8 { 9 ++r; 10 d=a[r].p-a[l].p; 11 continue; 12 } 13 if (a[l].s<d) 14 { 15 ans=min(ans,d-a[l].s); 16 --l; 17 d=a[r].p-a[l].p; 18 } 19 } 20 l=i-1,r=i;d=a[r].p-a[l].p; 21 while(l>0&&r<=n) 22 { 23 if (a[l].s>=d&&a[r].s>=d) 24 {puts("0");return 0;} 25 if (a[l].s<d) 26 { 27 --l; 28 d=a[r].p-a[l].p; 29 continue; 30 } 31 if (a[r].s<d) 32 { 33 ans=min(ans,d-a[r].s); 34 ++r; 35 d=a[r].p-a[l].p; 36 } 37 }
注意当前统计答案的是Bessie左边的干草堆,要把判断右边干草堆是否能跳过的语句写在判断左边干草堆的前面,同时,在处理右边的语句结尾加上continue,保证跳到不能再跳。如果一直continue到出界,则无论这边如何加固,另一边还是可以跳出去,没有统计答案,ans仍为无穷大,最后输出-1。