#include <iostream>
#include <cstdlib>

using namespace std;

int n;
int *Permutation;

bool IsSequen( void )
{
    for (int i=1; i<n; i++)
        if ((Permutation[i] - Permutation[i-1]) != 1)
                return false;
    return true;
}    

int FindMinEnd(int end)
{
    while (end > 0)
    {
        if (Permutation[end] > end )
            end --;
        else
            return end;
    }        
    
    return end;
}

int FindMaxBegin(int begin,int end)
{
    while ( begin < n-1)
    {
        if (Permutation[begin] < Permutation[end])
                begin ++;
        else
                return begin;
    }    
    
    return begin;
}      

int main()
{
    int t;
    int i;
    
    cin >> t;
    
    for (int j=0; j < t; j++)
    {
        cin >> n;
        
        Permutation = new int [n];
        int count = 0;
        for (i=0; i<n; i++)
            cin >> Permutation[i];
        
        if (IsSequen( ))
        {
           cout << 0 << endl;
           continue;   
        }    
        else
        {
            int MaxBegin = 0, MinEnd = n-1;
          
            do{
               MinEnd = FindMinEnd( n - 1);
               MaxBegin = FindMaxBegin ( 0 , MinEnd);
               
                if (MaxBegin == n-1 || MinEnd == 0)
                    break;
                else
                {
                    int temp = 0;
                    
                    temp = Permutation[MaxBegin];
                    Permutation[MaxBegin] = Permutation[MinEnd];
                    Permutation[MinEnd] = temp;
                    count ++;
                }     
                
                if (IsSequen())
                {
                    cout << count << endl;
                    break;
                }    
            }
            while (MaxBegin != MinEnd); 
            
             
        }    
         delete Permutation; 
    }    
    
    system("PAUSE");
    return 0;
}    

• Re:请教:Time Limit Exceeded (2253) lych 2005-12-10 15:03:39
  • Re:请教:Time Limit Exceeded (40) lych 2005-12-10 15:06:10
    • Re:请教:Time Limit Exceeded (52) frkstyc 2005-12-10 15:08:36
      • Re:请教:Time Limit Exceeded (28) lych 2005-12-12 00:00:51
        • Re:请教:Time Limit Exceeded (19) lych 2005-12-12 00:05:07
• 很简单的一道题,干嘛要写那么长啊,仔细地想想就可以AC了. (2) 61077798 2006-03-10 18:34:06
• Re:请教:Time Limit Exceeded (2253) luohuawusheng621 2012-03-04 21:51:56
• Re:请教:Time Limit Exceeded (2253) 991212746 2012-11-11 19:19:41