题解 P1588 【丢失的牛】

· · 题解

看到题解一溜溜全是搜索，这里发个带贪心的解题方法，而且是所有题解中最快的（0ms）

原题是FJ追牛，我们可以反过来想，变成牛追FJ，这样子，牛的移动方式有y+1，y-1，和直接y/2，因此我们在移动牛的时候可以优先考虑能否y/2，然后再考虑y+1,y-1的移动方式

之所以要反过来想是因为 在FJ追牛的时候是不能优先考虑x*2再考虑x+1，x-1的，也不能优先考虑x+1,x-1再考虑x*2！！

举个例子，FJ在25，牛在102，先*2再+1再*2共三步，FJ追牛的时候没办法优先考虑怎么走。但是如果是牛追FJ，牛可以直接y/2，这个时候牛的位置变成51，可以发现是奇数，没办法优先y/2，所以y-1变成50（y+1也要考虑），然后优先考虑y/2变成25，共三步。

代码~~

#include<iostream>
#include<queue>
using namespace std;

typedef pair<int,int> P;// p.first 表示牛的位置，p.second表示牛走了多少步 
queue<P> que;
P p;

int main(){
    int t, FJ, Min;
    cin >> t;
    while( t -- ){
        cin >> FJ >> p.first;
        Min = 1000000;
        que.push( P(p.first,0) );
        while( que.size() ){
            p = que.front();
            que.pop();
            if( p.first < FJ ){//如果牛在FJ的后面
                p.second += FJ - p.first;
                if( Min > p.second ) Min = p.second;
            }else if( p.first % 2 == 0 ){//牛可以直接除以2，优先考虑除以2 
                if( p.first / 2 > FJ )
                    que.push( P(p.first/2,p.second+1) );
                else if( p.first - FJ > FJ - p.first/2 )//除以2 之后距离FJ近一些 
                    que.push( P(p.first/2,p.second+1) );
                else{//除以2 之后距离FJ的距离反而变远了，因此不考虑除以2，直接走到FJ那里去 
                    p.second += p.first - FJ;
                    if( Min > p.second ) Min = p.second;
                }
            }else{//如果不能直接y/2，选择y+1，y-1的方式 
                que.push( P(p.first+1,p.second+1) );
                que.push( P(p.first-1,p.second+1) );
            }
        }
        cout << Min << endl;
    }
    return 0;
}

个人喜欢用队列来记录数据，也可以采用其他方法