P2907 [USACO08OPEN] Roads Around The Farm S

题目描述

Farmer John 的奶牛对探索农场周围的领地产生了兴趣。最初，所有 $N$ 头奶牛（$1 \leq N \leq 10^9$）以一个大群体的形式开始沿着一条道路旅行。当遇到岔路时，群体有时会选择分成两个较小的（非空）群体，每个群体沿着一条道路继续前进。当其中一个群体到达另一个岔路时，它可能会再次分裂，依此类推。

奶牛们设计了一种特殊的分裂方式：如果它们可以分裂成两个群体，使得群体的大小正好相差 $K$（$1 \leq K \leq 1000$），那么它们就会以这种方式分裂；否则，它们就停止探索，开始安静地吃草。

假设总是会有新的岔路，计算最终安静吃草的奶牛群的数量。

输入格式

两个空格分隔的整数，$N$ 和 $K$。

输出格式

一个整数，表示安静吃草的奶牛群的数量。

输入输出样例 #1

输入 #1

6 2

输出 #1

说明/提示

有 $6$ 头奶牛，群体大小的差异是 $2$。

最终有 $3$ 个群体（分别有 $2$、$1$ 和 $3$ 头奶牛）。

  6/ \
2   4/ \1   3

（由 ChatGPT 4o 翻译）
就是一个比较简单的递归吧。。。
首先牛群的数量就是分成不同群体的次数再+1，就直接定义ans=1了
假设分出来的两个牛群中，数量较多的是x，数量较少的y
那么x=(n+k)/2, y=(n-k)/2
则 x-y=k,x+y=n
得到2x=n+k;
所以递归的终止条件就是n+k不是偶数了。不是偶数怎么分成两群牛呢？？？
还有，当x<=0或x>=n的时候递归也终止，怎么可能牛的数量小于0或一群牛的数量大于所有牛的数量呢？
对于y，这也是成立的，所以y<=0或y>=n也是终止条件
否则，ans++, 继续调用x和y
代码如下↓
#include<iostream> using namespace std; int n,k; int ans=1; void f(int n){ int x=(n+k)/2; int y=n-x; if((n+k)%2!=0) return ; else{ if(x<=0||x>=n) return; if(y<=0||y>=n) return ; ++ans; f(x); f(y); } } int main(){ cin>>n>>k; f(n); cout<<ans<<endl; return 0; }
就这样了。。。也就嘛嘛。。。
（最近在打音游，求键盘推荐。我用的迈从Ace60 蓝冰磁轴手感真的不戳儿~就是有点吵啊喂）

USACO08 OPEN Roads Around the Farm S (递归)