程序竞赛题解答.cpp

全班有N（2<=N<=45）个人排成一排

#if 0
C题  排  队
【问题描述】
全班有N（2<=N<=45）个人排成一排，但因为高矮不齐，需要进行调整。调整的方法是，不调换左右次序，只让若干人后退一步变为第2排，使第一排留下的人从左到右的身高按降序排列，即右边的人不比左边的人高。如果第2排的人还不按降序排列，则照此办理，即再让第2排的若干人后退一步变为第3排，这样继续下去，直到所有排的人都按身高从高到低排列。
  调整中，你需要找出一种使第一排留下的人数尽可能多的调整方法，第二排若需要继续调整，则也应使第二排留下的人数尽可能多，余类推。

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

【输出】
   对于每组测试数据输出应该是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

#endif
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char *argv[])
{
    FILE *fp;
    char buf[40];
    int i=0,j=1,n,s[40],index,mmax,mxy,col=0,tmp,mm,tmp1,tmp2,mmin,nn=0;
    int Q[40],first=0,last=1;
    bool ok=true,oo=true;
    fp=fopen("dl.in","r");
    fgets(buf,40,fp);
    sscanf(buf,"%d",&n);
    memset(s,0,40*sizeof(int));
    fgets(buf,40,fp);
    while(buf[i]!='\n')  //读取数据 (方法烦啦)
    {
        if(buf[i]!=' ')  {s[j]=s[j]*10;s[j]=s[j]+(buf[i]-'0');}
        else j++;
        i++;
    }
    for(i=1;i<=n;i++) cout<<s[i]<<" ";
    cout<<endl;
begin:
    mmax=0;mmin=0;
    if(ok) {index=1;first=last=1;Q[last++]=index;ok=false;}
    mmin++;
    while(first<last)
    {
        tmp=s[index];
        for(i=index;i>1;i--)
        {
           if(s[i]>=tmp) {mmin++;tmp=s[i];}
           else 
          {
              if(index==1) Q[last++]=i;
          }
        }
        tmp=s[index];
        for(i=index+1;i<=n;i++)
        {
           if(s[i]<=tmp) {mmin++;tmp=s[i];}
           else
           {
               if(index==1) Q[last++]=i;
           }
        }
        if(mmax<mmin) {mmax=mmin;mxy=index;}
        index=Q[++first];mmin=0;mmin++;
    }    
    if(oo) {cout<<"Man= "<<mmax<<endl;oo=false;}
    col++;
    tmp=Q[mxy];
    for(i=mxy-1;i>1;i--) if(Q[i]>tmp) {tmp=Q[i];mm=i;}
    tmp1=tmp2=Q[mxy];
    for(i=1;i<=last-1 && i!=mxy;i++)
    {
        if(i>mxy && Q[i]<tmp1) {s[i]=Q[i];tmp1=Q[i];nn++;}
        if(i>=mm && i<mxy && Q[i]>tmp2) {s[i]=Q[i];nn++;}
    }
    if(last>2) {n=nn;ok=true;goto begin;}
    cout<<"Low= "<<col<<endl;
    fclose(fp);
    system("PAUSE");
    return EXIT_SUCCESS;
}

//另外的方法 可以从后面开始 每个数据编号 规则是此数要>=后面的数  且此数的编号是最大