USACO2008 Roads Around The Farm /// queue 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

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=;

    q.push(n);

    while(!q.empty())

    {

        int m=q.front();

        if( m>k && (m-k)%== )

        {

            q.push((m-k)/);

            q.push((m-k)/+k);

        }

        else cnt++;

        q.pop();

    }

    printf("%d\n",cnt);

    return ;

}

巴特西

USACO2008 Roads Around The Farm /// queue oj23321

最新文章

热门文章