game.cpp

2002年ACM Asia-BeiJing的比赛题目及原创算法解决方案：Game Prediction

#include <fstream.h>

int max(int me[],int signme[],int n){
   for(int i=1;i<=n;i++){
      if(signme[i]==0){
         me[0]=i;
         return me[i];
      }
   }
   return 0;
}

int min(int me[],int signme[],int n){
   for(int i=n;i>=1;i++){
      if(signme[i]==0){ return i; }
   }
   return 0;
}

int search(int super[],int signsuper[],int me,int n){
   int pre;
   for(int i=1;i<=n;i++){
      if(signsuper[i]==0){
         if(super[i]<me){
            return pre;
         }
         pre=i;
      }
   }
   return 0;

}

void sort(int me[],int n){
   int temp;
   for(int i=1;i<=n;i++){
      for(int j=1;j<=(n-i);j++) {
         if(me[j]<me[j+1]){temp=me[j];me[j]=me[j+1];me[j+1]=temp;}
      }
   }
}

int main(){
   ifstream fin;
   fin.open("game.in");
//   ofstream fout;
//   fout.open("game.out");

   int m,n;
   int casenum=1;
   int me[52];
   int super[52];
   int sign[52*20];
   int signme[52],signsuper[52];
   int num;

   int i,j;
   fin>>m>>n;
   while(m!=0&&n!=0){
      for(i=1;i<=n*m;i++) sign[i]=0;
      for(i=1;i<=n;i++){
         fin>>me[i];
         sign[me[i]]=1;
      }
      for(i=n*m,j=1;i>=1&&j<=n;i--){
         if(sign[i]==0) super[j++]=i;
      }
      sort(me,n);
      num=0;
      for(i=1;i<=n;i++){signme[i]=0;signsuper[i]=0;}
    for(i=1;i<=n;i++){
      if(max(me,signme,n)>max(super,signsuper,n)){
         signme[me[0]]=1;
         signsuper[min(me,signme,n)]=1;
         num++;
      }
      else{
         signme[me[0]]=1;
         signsuper[search(super,signsuper,me[me[0]],n)]=1;
      }
    }
      cout<<"Case "<<casenum<<": "<<num<<endl;
      casenum++;
//      fout<<num<<endl;
      fin>>m>>n;
   }
   fin.close();
   return 1;
}