搜索专题:Balloons

搜索专题:Balloons

这道题一看与时间有关，第一想到的就是BFS，定义一个状态，包含每一个状态的剩余气球数，已经进行的时间和每一个志愿者上一次吹气球的时间；
每一次状态转换时，检查是否有没有使用的志愿者，或者是已经休息结束可以进行下一轮吹气球的志愿者，如果没有，就将进行的时间加一，进入下一个状态；第一次写的code超时，主要是没考虑最优结果，在还有志愿者可以使用的时候没有使用，而是又入一次队，导致无形中增加了无数的冗余状态；
代码如下：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

const int N = 10 + 5;

int per[10][2],m,n;///Ai,Bi

typedef struct node{              //定义一个状态

    int step,left;

    int start[N];

    node(){memset(start,-1,sizeof(start));}//没有使用的志愿者标记为-1

    bool operator < (const node x)const {

        return step > x.step;      //最小耗时优先拓展

    }

}Node;

int BFS(){

    priority_queue<Node> Q;

    Node t,s;

    bool can_updata;

    t.step = 0;

    t.left = m;

    Q.push(t);

    while(!Q.empty()){

        t = Q.top();Q.pop();

        if(t.left <=0 ) return t.step;

        can_updata = false;

        for(int i=0;i<n;i++){ //如果有没有使用的志愿者或有可以继续工作的志愿者则添加新状态

            if(t.start[i]<0 || t.step - t.start[i] >= per[i][1]){

                can_updata = true;//是否更新标志

                s = t;

                s.left = t.left - per[i][0];

                s.step = t.step + 1;

                s.start[i] = s.step;

                Q.push(s);

            }

        }

        if(!can_updata){//如果全部志愿者还在休息,则时间加1

            s = t;

            s.step = t.step + 1;

            Q.push(s);

        }

    }

    return -1;

}

int main(){

    scanf("%d %d",&m,&n);

    for(int i=0;i<n;i++)

        scanf("%d %d",&per[i][0],&per[i][1]);

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

}

//如有错误，还请各位指出