关于lis/dls的一个疑问
  • 板块学术版
  • 楼主Cocoly1990
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/7/28 23:39
  • 上次更新2023/11/4 12:48:17
查看原帖
关于lis/dls的一个疑问
183026
Cocoly1990楼主2021/7/28 23:39

如果使用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 ; 
}
2021/7/28 23:39
加载中...