[Codeforces Round #817 (Div. 4)] D. Line

 

 

---

※. 최선의 경우는 mid를 기준으로 왼쪽은 전부 R, 오른쪽은 L이 되는 것이다.

 

※. 총합은 L일 경우 index를 더해주고 R일 경우 N-index-1을 더해준다.

 

※. 방향을 바꾸는 우선순위는 바꿨을 때 가장 큰 수부터 변경하면 된다.

L이라면 R로 변경할 때 L의 기존값(index)를 빼주고 R의 값 N-index-1을 더해준다.

(변경값 v = (N-index-1) - index)

R이라면 L로 변경할 때 R의 기존값(N-index-1)을 빼주고 L의 값 index를 더해준다.

(변경값 v = index - (N-index-1)

 

※. 변경값들이 양수라면 변경했을 때 기존값보다 커진다는 뜻이다. 이 변경값을 내림차순 정렬한 뒤 순서대로 ans에다

더해주면 된다. (변경값은 기존의 값을 이미 빼준 값이다. 따라서 현재의 값을 빼준 뒤 변경값을 더해줄 필요가 없다.)

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

public class Main {
	static long ans;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			int N = Integer.parseInt(br.readLine());
 			char[] strarr = br.readLine().toCharArray();
 			ans = 0;
 			long[] v = new long[N];
 			for(int i = 0; i < N; i++) {
 				if(strarr[i] == 'L') {
 					v[i] = (N-1-i) - i;
 					ans += i;
 				}
 				else {
 					v[i] = i-(N-1-i);
 					ans += N-i-1;
 				}
 			}
 			
 			Arrays.sort(v);
 			for(int i = N-1; i >= 0; i--) {
 				if(v[i] > 0) {
 					ans += v[i];
 				}
 				sb.append(ans).append(" ");
 			}
 			sb.append('\n');
 		}
 		System.out.println(sb);
 	}
}