以下代码:
cl数组:到达i时共有多少个朝向左边的箭头
cr数组:到达i时共有多少个朝向右边的箭头
sum_l:到达i时所有朝向左侧的箭头的下标和
sum_r:到达i时所有朝向右侧的箭头的下标和
以下代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <string.h>
using namespace std ;
int t , n , pl , pr ,pre_l[500005] , pre_r[500005] , sum_l[500005] , sum_r[500005] ;
int main(){
cin >> t ;
while( t -- ){
pl = pr = 1 ;
memset(pre_l , 0 , sizeof(pre_l));
memset(pre_r , 0 , sizeof(pre_r));
memset(sum_l , 0 , sizeof(sum_l));
memset(sum_r , 0 , sizeof(sum_r));
cin >> n ;
char p ;
for( int i = 1 ; i <= n ; i ++ ){
cin >> p ;
if( p == '<' ){
pre_l[i] ++ ;
pre_l[i] += pre_l[i-1] ;
pre_r[i] = pre_r[i-1] ;
}else{
pre_r[i] ++ ;
pre_r[i] += pre_r[i-1] ;
pre_l[i] = pre_l[i-1] ;
}
}
for( int i = 1 ; i <= n ; i ++ ){
if( pre_r[i] > pre_r[i-1] ){
sum_r[pr] += i ;
sum_r[pr] += sum_r[pr-1] ;
pr ++ ;
}else{
sum_r[pr] = sum_r[pr-1] ;
pr ++ ;
}
if( pre_l[i] > pre_l[i-1] ){
sum_l[pl] += i ;
sum_l[pl] += sum_l[pl-1] ;
pl ++ ;
}else{
sum_l[pl] = sum_l[pl-1] ;
pl ++ ;
}
}
for( int i = 1 ; i <= n ; i ++ ){
int ans = 0 ;
//如果这里是向左的
if( pre_l[i] > pre_l[i-1] ){
if( pre_r[i] > ( pre_l[n] - pre_l[i+1])){
//若最后是从右侧跑出
ans = (i + n + 1 + 2 * ( sum_l[pl] - sum_r[pl+1])) ;
}else{
//若最后是从左侧跑出
ans = (i + 2 * (sum_l[pl] - sum_r[pl])) ;
}
}
//如果这里是向右的
if( pre_l[i] == pre_l[i-1] ){
if(pre_r[i-1] > ( pre_l[n] - pre_l[i])){
//若最后从右侧跑出
ans = (2 * ( sum_l[pl] - sum_r[pl]) )+ n + 1 - i ;
}else{
//若最后从左侧跑出
ans = ( 2 * ( sum_l[pr+1] - sum_r[pr])) - i;
}
}
printf("%d " , ans );
}
printf("\n");
for( int i = 1 ; i <= pl ; i ++ ){
cout << sum_l[i] << " ";
}
cout << endl;
for( int i = 1 ; i <= pr ; i ++ ){
cout << sum_r[i] << " ";
}
cout <<endl;
for( int i = 1 ; i <= n ; i ++ ){
cout << pre_l[i] << " " ;
}
cout << endl;
for ( int i = 1 ; i <= n ; i ++ ){
cout << pre_r[i] << " " ;
}
cout << endl << endl;
}
return 0 ;
}
感谢大佬!好人一生平安!