【算法】第五届北京复赛试题

水晶之夜 发布于 2014/02/17 08:48
阅读 431
收藏 1

这是一个以前的竞赛题目。题目如下:

【问题描述】

全班有N(2<=N<=45)个人排成一排,但因为高矮不齐,需要进行调整。调整的方法是,不调换左右次序,只让若干人后退一步变为第2排,使第一排留下的人从左到右的身高按降序排列,即右边的人不比左边的人高。如果第2排的人还不按降序排列,则照此办理,即再让第2排的若干人后退一步变为第3排,这样继续下去,直到所有排的人都按身高从高到低排列。

调整中,你需要找出一种使第一排留下的人数尽可能多的调整方法,第二排若需要继续调整,则也应使第二排留下的人数尽可能多,余类推。

【输入】输入文件名“sortin.txt

输入文件第一行为一个整数M,表示有M组测试数据。接下来的每两行为一组测试数据,每组测试数据的第一行为一个整数N,表示该组测试数据的人数;接下来的一行是这N个人的身高,以厘米为单位,且都为整数,每个数用空格隔开。

【输出】输出文件名“sortout.txt

   对于每组测试数据输出应该是2行:

   第一行:第一排留下的人数Man;

   第二行:最后调整完共有几排Low。(具体格式请严格按照样例输出进行)

程序运行后结果示例:

【样例输入】

 3

 8

 130 122 112 126 126 125 120 100

 5

 187 187 178 165 164

 5

 187 187 178 165 167

【样例输出】

Man=6

Low=2

Man=5

Low=1

Man=4

Low=2


关于文件读取写入的问题我不问,主要是算法如何解决。我想的方法太复杂了,难以实现。

主要是“为了使第一排留下的人最多”,这个来怎么表示,如果说用一个数组来保存每排剩下的人数的话,我无法记录下剩下人数所对应的情况(可能要用二维数组来保存)。总之,算法太复杂,难以实现,求一个简单易理解的算法。

加载中
0
为梦而来
为梦而来
  1. 在一个论坛上看到的可以参考一下
  2. #endif   
  3. #include <cstdlib>   
  4. #include <iostream>   
  5. #include <string>   
  6. using namespace std;   
  7.    
  8. int main(int argc, char *argv[])   
  9. {   
  10.     FILE *fp;   
  11.     char buf[40];   
  12.     int i=0,j=1,n,s[40],index,mmax,mxy,col=0,tmp,mm,tmp1,tmp2,mmin,nn=0;   
  13.     int Q[40],first=0,last=1;   
  14.     bool ok=true,oo=true;   
  15.     fp=fopen("dl.in","r");   
  16.     fgets(buf,40,fp);   
  17.     sscanf(buf,"%d",&n);   
  18.     memset(s,0,40*sizeof(int));   
  19.     fgets(buf,40,fp);   
  20.     while(buf[i]!='\n')  //读取数据 (方法烦啦)   
  21.     {   
  22.         if(buf[i]!=' ')  {s[j]=s[j]*10;s[j]=s[j]+(buf[i]-'0');}   
  23.         else j++;   
  24.         i++;   
  25.     }   
  26.     for(i=1;i<=n;i++) cout<<s[i]<<" ";   
  27.     cout<<endl;   
  28. begin:   
  29.     mmax=0;mmin=0;   
  30.     if(ok) {index=1;first=last=1;Q[last++]=index;ok=false;}   
  31.     mmin++;   
  32.     while(first<last)   
  33.     {   
  34.         tmp=s[index];   
  35.         for(i=index;i>1;i--)   
  36.         {   
  37.            if(s[i]>=tmp) {mmin++;tmp=s[i];}   
  38.            else    
  39.           {   
  40.               if(index==1) Q[last++]=i;   
  41.           }   
  42.         }   
  43.         tmp=s[index];   
  44.         for(i=index+1;i<=n;i++)   
  45.         {   
  46.            if(s[i]<=tmp) {mmin++;tmp=s[i];}   
  47.            else   
  48.            {   
  49.                if(index==1) Q[last++]=i;   
  50.            }   
  51.         }   
  52.         if(mmax<mmin) {mmax=mmin;mxy=index;}   
  53.         index=Q[++first];mmin=0;mmin++;   
  54.     }       
  55.     if(oo) {cout<<"Man= "<<mmax<<endl;oo=false;}   
  56.     col++;   
  57.     tmp=Q[mxy];   
  58.     for(i=mxy-1;i>1;i--) if(Q[i]>tmp) {tmp=Q[i];mm=i;}   
  59.     tmp1=tmp2=Q[mxy];   
  60.     for(i=1;i<=last-1 && i!=mxy;i++)   
  61.     {   
  62.         if(i>mxy && Q[i]<tmp1) {s[i]=Q[i];tmp1=Q[i];nn++;}   
  63.         if(i>=mm && i<mxy && Q[i]>tmp2) {s[i]=Q[i];nn++;}   
  64.     }   
  65.     if(last>2) {n=nn;ok=true;goto begin;}   
  66.     cout<<"Low= "<<col<<endl;   
  67.     fclose(fp);   
  68.     system("PAUSE");   
  69.     return EXIT_SUCCESS;   
  70. }   
0
白文
白文
失误,把整个帖子删除了
白文
白文
想改几个错字,手机客户端竟然是全删
0
白文
白文
以数组第一项为基准,小的留下,大的放下一排,使每个新建的数组降序,最后进行归并排序,时间复杂度O(nlogn)
白文
白文
@水晶之夜 这个我还在想,有一种蛮力算法,效率不高,扫描整个数组,统计后面的次序,代价太大
水晶之夜
水晶之夜
关键就是 题目中要求“使第一排的人数尽可能最多”这个条件,这个条件就说明算法需要考虑到多种可能性,在这些可能性中选一个人数最多的情况。这一点在程序中如何体现
白文
白文
@Shazi199 保证最多数量可以以寻找中位数的方法,只能保证前几排,后最后几排就比较困难,依赖于初始序列。一般情况下,以第一排作基准,在初始序列分布均匀的情况,基本能保证第一排的数量。这个方法提升有限,快速排序中只能削减常数级的时间,我没有想到更好的办法
返回顶部
顶部