搜索专题:Balloons

这道题一看与时间有关，第一想到的就是BFS，定义一个状态，包含每一个状态的剩余气球数，已经进行的时间和每一个志愿者上一次吹气球的时间；

每一次状态转换时，检查是否有没有使用的志愿者，或者是已经休息结束可以进行下一轮吹气球的志愿者，如果没有，就将进行的时间加一，进入下一个状态；第一次写的code超时，主要是没考虑最优结果，在还有志愿者可以使用的时候没有使用，而是又入一次队，导致无形中增加了无数的冗余状态；

代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 10 + 5;int per[10][2],m,n;///Ai,Bitypedef 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
         
           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
          
           = 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