USACO2008 Roads Around The Farmqueue oj23321

题目大意：

N (1 ≤ N ≤ 1,000,000,000)牛群在遇到岔路时，若能分为恰好相差 K (1 ≤ K ≤ 1000)的两路，则持续分裂（假设会一直遇到岔路），否则停止开始吃草。

Input

* Line 1: Two space-separated integers: N and K

Output

* Line 1: A single integer representing the number of groups of grazing cows

Sample Input

6 2

Sample Output

3

Hint

SAMPLE INPUT DETAILS:

There are 6 cows and the difference in group sizes is 2.

SAMPLE OUTPUT DETAILS:

There are 3 final groups (with 2, 1, and 3 cows in them).

  6 /  \2   4    /  \   1   3

一开始直接随着分裂记录结果 结果一直WA 

看了题解才恍然 其实遍历完所有的结果

记录下 不符合继续分裂条件 的结果个数其实就是最后的答案

#include <bits/stdc++.h> using namespace std; int main() { int n,k,cnt; queue <int> q; scanf("%d%d",&n,&k); while(!q.empty()) q.pop(); cnt=0; q.push(n); while(!q.empty()) { int m=q.front(); if( m>k && (m-k)%2==0 ) { q.push((m-k)/2); q.push((m-k)/2+k); } else cnt++; q.pop(); } printf("%d\n",cnt); return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8359286.html

相关资源：JAVA上百实例源码以及开源项目