【Luogu P3124】【USACO15OPEN】Trapped in the Haybales S

首先找到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。

 

上一篇:Hibernate查询oracle数据库char类型字段,获取不到结果的问题


下一篇:2021-01-04 USACO Wormholes