CF Gym 100637B Lunch(拆分子问题)

时间:2023-03-09 18:59:29
CF Gym 100637B 	Lunch(拆分子问题)

题意:在一条狭窄的沼泽上有一列数量为n的连续荷叶,编号为1-n。有一只蛤,在边s号荷叶上,其他荷叶上苍蝇,哈可以跳到相邻的荷叶上,或者越过一片荷叶,跳完以后原来的荷叶会沉,目标是f荷叶,在跳到f荷叶之前要吃掉其他所有的苍蝇。在这个前提下,希望尽量少跳相邻的荷叶,输出跳相邻荷叶的次数。

题解:分析先考虑一般情况

CF Gym 100637B 	Lunch(拆分子问题)

s和f把区间分成了三段,首先看左区间。由于不可能跳过连续两片荷叶,那么最后一定是要落在s左边相邻的位置上,那么对于左边的区间等效为一个子问题:

CF Gym 100637B 	Lunch(拆分子问题)

右区间和左边是对称的,情况类似,

如果左区间存在的话,那么中间区间的s应该加1,类似的,如果右区间存在,那么f应该减1

则中间区间的问题等效为:

当然如果中间没有格子的话,而且两边都有,那么f会叠加到s‘,这时候是无解的。

CF Gym 100637B 	Lunch(拆分子问题)

接下来我们来分析这些子问题:

对于第一个子问题:最多跳一次,先跳奇数位置,到跳到头了跳一次相邻位置变成偶数位置在跳回来。

对于第二个:

CF Gym 100637B 	Lunch(拆分子问题)

由于在左边跳完之前是不能跳相邻格子的,否则出现一个大于1的间隔,而且可以发现,每三个格子最少是跳一次,而且跳完了以后和之前的问题性质类似。

最后小于3的分别讨论一下就ok了。

#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<algorithm> using namespace std;
typedef long long ll; int main()
{
int n,s,f;
scanf("%d%d%d",&n,&s,&f);
if(f<s) swap(f,s); if(s+==f){
if(s>&&f<n){
printf("-1"); return ;
}
printf(""); return ;
}
int ans = ;
if(s>) ans++,s++;
if(f<n) ans++,f--;
ans += (f-s)/+(f-s)%;
printf("%d",ans);
return ;
}