正经题解｜奶牛分群

【算法分析】

分析题目发现，可以进行递归。$dfs(x)$ 里返回将 $x$ 只牛分裂会有几群牛在平静地吃草。递归终止条件是当这群牛的数目小于等于 $k$，或者不能分裂成两堆时。

【参考代码】

#include<bits/stdc++.h>
using namespace std;
int n,k;

int dfs(int x){
	if(x<=k || (x-k)%2==1){
		return 1;
	}
	return dfs((x-k)/2)+dfs((x+k)/2); 
}
int main(){
	cin>>n>>k;
	cout<<dfs(n); 
	return 0;
}

【时间复杂度】

$O(logn)$

【预计得分】

$100pts$