萌新求教
查看原帖
萌新求教
120855
清雅流水楼主2020/7/12 18:57

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 ;
}
2020/7/12 18:57
加载中...