图解参见
https://www.acwing.com/solution/AcWing/content/5351/
AcWing136
const int N = 10002;
typedef long long LL;
int ver [N][2], p [N], pneg [N];
LL raw [N], st [N], o [N];
inline bool cmp ( int a, int b ){ return raw [a] < raw [b]; }
inline void lnk ( int u, int v ){ ver [u][1] = v; ver [v][0] = u; }
inline void del ( int u ){
int pr = ver [u][0], nx = ver [u][1];
ver [pr][1] = nx; ver [nx][0] = pr;
}
int main (){
int T; rd ( T );
while ( T-- ){
int id, n; rd ( id ); rd ( n ); printf ( "%d %d", id, (n+1)>>1 );
for ( int i = 1; i <= n; ++i ) lrd ( raw [i] );
for ( int i = 1; i <= n; ++i ) st [i] = raw [i];
sort ( st+1, st+n +1 );
for ( int i = 1; i <= n; ++i ) pneg [i] = i;
sort ( pneg+1, pneg+n +1, cmp );
for ( int i = 1; i <= n; ++i ) p [ pneg[i] ] = i;
memset ( ver, 0, sizeof ( ver ) );
for ( int i = 1; i < n; ++i ) lnk ( i, i+1 );
lnk ( 0, 1 ); lnk ( n, N-1 );
o [0] = 0; int midp = (n+1)>>1, prd = 0, nxd = 0;
for ( int i = n;; --i ){
if ( i&1 ){
if ( i!=n ){
if ( prd == 1 && nxd == 1 ) prd = nxd = 0;
else if ( prd == 2 ){ midp = ver [midp][1]; prd = nxd = 0; }
else if ( nxd == 2 ){ midp = ver [midp][0]; nxd = prd = 0; }
}
o [++o[0]] = st [midp];
}
if ( i == 3 ) break;
if ( p [i] > midp ) nxd ++;
else if ( p [i] < midp ) prd ++;
else{ nxd ++; prd ++; }
del ( p [i] );
}
o [++o[0]] = raw [1];
int cnt = 0;
for ( int i = o [0]; i >= 1; --i ){
if ( cnt % 10 == 0 ) puts ("");
printf ( "%lld ", o [i] );
cnt ++;
}
if ( cnt % 10 ) puts ("");
}
return 0;
}
只放代码果然还是太不负责了,说不知道该说什么只是在骗自己罢了(划掉)。
大家加油学,不会私信我。
106???