Codeforces 1238C Standard Free2play 题解
题意
有一个高为$h (1\le h\le10^9)$的悬崖,在高度为$x(1\le x\le h)$的位置上,有一个可移动的平台。
每个平台有两种状态:隐藏在悬崖里 或 在悬崖外。一开始,有$n (1\le n\le\min(h,2\cdot10^5))$个在悬崖外的平台,分别为$p_1,p_2,\dots,p_n$,其中$p_1=h$。
你一开始站在$p_1$上,即在悬崖最高点$h$。若你站在高度为$x$的地方(高度为$x$的平台必须在悬崖外),你可以按下一个按钮。如果你按下了按钮,那么高度为$x$和$x-1$的平台的状态会改变,即高度为$x$的平台隐藏到悬崖里,若高度为$x-1$的平台在悬崖里,则它移动到悬崖外;若它在悬崖外,则隐藏到悬崖里。如果按下按钮后,高度为$x-1$的平台在悬崖外,那么你安全地落在高度为$x-1$的平台上(否则你会掉落在下一个在悬崖外的平台上)。这是唯一一种方式从一个平台移动到另外一个平台。
你可以安全地从$x$掉落到$x-2$,但是如果从$x$掉落在$x-3$或更低处,你就死了。
你可以使用魔法。一次魔法只能使在任何高度的平台改变状态(除了高度为$h$的平台)。
求你使用魔法的最小次数,使得你安全地落在地上(即高度为$0$的地方)。
题解
首先,若你在高度为$x$的平台上,下一个在悬崖外平台的高度为$y$且$x>y+1$,那么你可以安全地、不使用任何魔法,从$x$到达$y+1$。
现在要考虑的是,你在高度为$x$的平台上,有多个连续的、在悬崖外的平台,设它们的高度为$q_1,q_2,\dots,q_n$且$q_1=x,\forall 1\le i<n,q_i=q_{i+1}+1$。
- 若$n$为奇数,则可以安全地、不使用任何魔法,从$q_1$到达$q_n$(因为每次按下按钮,都只会掉下$2$格)。
- 若$n$为偶数,则需要一次魔法(如果不使用魔法,在$q_{n-1}$按下按钮时,会掉下$2$格以上),把高度为$q_n+1$的平台移动到悬崖外。
注意,当$q_n=1$时,可以不需要魔法,直接掉落$2$格到地面。
程序
1 | // #pragma GCC optimize(2) |