如果使用STL二分法,进行更换是否会导致最后做出来的序列不是有序的?如果可以保证有序,那么请问这份代码的问题在哪(合唱队列)
#include<bits/stdc++.h>
using namespace std ;
int n , a[107] , d[107] , ans , res , len ;
int main()
{
cin >> n ;
res = -1 ;
for( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
//sort(a + 1 , a + n + 1 ) ;
//for( int i = 1 ; i <= n ; i ++ ) cout << a[i] << " " ;
for( int i = 1 ; i <= n ; i ++ )
{
//int i = 20 ;
ans = 0 ;
d[1] = a[1] ;
len = 1 ;
for( int j = 2 ; j <= i ; j ++ )
{
if( d[len] < a[j] ) d[ ++ len ] = a[j];
else
{
int p ;
p = lower_bound( d + 1 , d + 1 + len , a[j] , less<int>() ) - d ;
d[p] = a[j];
}
}
ans += len ;
cout << len << " " ;
d[1] = a[n] ;
len = 1 ;
for( int j = n - 1 ; j >= i ; j -- )
{
if( d[len] > a[j] ) d[ ++ len ] = a[j];
else
{
int p ;
p = lower_bound( d + 1 , d + 1 + len , a[j] , greater<int>() ) - d ;
d[p] = a[j];
}
//for(int i = 1 ; i <= len ; i ++) cout << d[i] << " " ;
//cout << endl ;
}
ans += len ;
cout << len << endl ;
res = max(res , ans) ;
//for(int i = 1 ; i <= 17 ; i ++) cout << d[i] << " " ;
}
cout << ans - res + 1 ;
return 0 ;
}