0分全WA,样例与题解中提到的
20
BGBGBGGGBGGBGBBGBGGB
4 2 4 3 5 4 6 3 6 3 2 6 7 3 5 2 9 5 1 5
两组数据都能通过,求强数据
code:
#include <bits/stdc++.h>
using namespace std ;
struct node1
{
int js , le , ri ;
bool xb , ky ;
} a[200010] ;
struct node2
{
int bl , br , cz ;
bool operator < ( const node2 & a ) const
{
if( cz == a.cz )
{
return bl > a.bl ;
}
return cz > a.cz ;
}
} wz , tmp ;
int n ;
int dl[200010] , dr[200010] , ld ;
int main ()
{
cin >> n ;
char c ;
for( int i = 0 ; i < n ; i ++ )
{
cin >> c ;
if( c == 'B' )
{
a[i].xb = 0 ;
}
else
{
a[i].xb = 1 ;
}
if( i == 0 ) a[i].le = -1 ;
else a[i].le = i - 1 ;
if( i == n - 1 ) a[i].ri = -1 ;
else a[i].ri = i + 1 ;
a[i].ky = 1 ;
}
priority_queue <node2> q ;
for( int i = 0 ; i < n ; i ++ )
{
cin >> a[i].js ;
if( i > 0 && a[i].xb != a[i - 1].xb )
{
wz.cz = abs( a[i].js - a[i - 1].js ) ;
wz.bl = i - 1 ;
wz.br = i ;
q.push( wz ) ;
}
}
while( !q.empty() )
{
do
{
// cout<< wz.bl << ' ' << wz.br << ' ' << wz.cz << ' ' << a[wz.bl].js << ' ' << a[wz.br].js << endl ;
wz = q.top() ;
q.pop() ;
}
while( !q.empty() && ( a[wz.bl].ky == 0 || a[wz.br].ky == 0 ) ) ;
if( a[wz.bl].ky == 0 || a[wz.br].ky == 0 ) break ;
// cout<< endl ;
// cout<< wz.bl << ' ' << wz.br << ' ' << wz.cz << ' ' << a[wz.bl].js << ' ' << a[wz.br].js << endl ;
// cout<< endl << endl ;
a[wz.bl].ky = a[wz.br].ky = 0 ;
dl[ld] = wz.bl ;
dr[ld] = wz.br ;
ld ++ ;
if( a[wz.bl].le != -1 ) a[a[wz.bl].le].ri = a[wz.br].ri ;
if( a[wz.br].ri != -1 ) a[a[wz.br].ri].le = a[wz.br].le ;
if( a[a[wz.bl].le].xb != a[a[wz.br].ri].xb )
{
tmp.bl = a[wz.bl].le ;
tmp.br = a[wz.br].ri ;
tmp.cz = abs( a[a[wz.bl].le].js - a[a[wz.br].ri].js ) ;
q.push( tmp ) ;
}
}
cout<< ld << endl ;
for( int i = 0 ; i < ld ; i ++ )
{
cout<< dl[i] + 1 << ' ' << dr[i] + 1 << endl ;
}
return 0 ;
}