Problem - D - Codeforces
codeforces.com
절반을 나눠서
왼쪽 부분에 있는 사람이 오른쪽을 보고
오른쪽 부분에 있는 사람이 왼쪽을 봐야
최대값을 가진다
- 제목
Line
- 조건
time limit per test : 2 second
memory limit per test : 256 megabytes
input : standard input
output : standard output
- 문제
There are n people in a horizontal line, each looking either to the left or the right. Each person counts the number of people in the direction they are looking. The value of the line is the sum of each person's count.
For example, in the arrangement LRRLL, where L stands for a person looking left and R stands for a person looking right, the counts for each person are [0,3,2,3,4], and the value is 0+3+2+3+4=12.
You are given the initial arrangement of people in the line. For each k from 1 to n, determine the maximum value of the line if you can change the direction of at most k people.
- 입력
The input consists of multiple test cases. The first line contains an integer t (1≤t≤100) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer n (1≤n≤2⋅10^5) — the length of the line.
The following line contains a string consisting of n characters, each of which is either L or R, representing a person facing left or right, respectively — the description of the line.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.
Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
- 출력
For each test case, output n space-separated non-negative integers — the maximum value of the line if you can change the direction of at most k people for each k from 1 to n, inclusive.
| 예제 입력1 | 예제 출력1 |
| 6 3 LLR 5 LRRLL 1 L 12 LRRRLLLRLLRL 10 LLLLLRRRRR 9 LRLRLRLRL |
3 5 5 16 16 16 16 16 0 86 95 98 101 102 102 102 102 102 102 102 102 29 38 45 52 57 62 65 68 69 70 44 50 54 56 56 56 56 56 56 |
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define endl '\n'
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string str;
int tc, sz;
cin >> tc;
while(tc--){
cin >> sz >> str;
long long sum = 0;
vector<long long> changeVal;
for(int n = 0 ; n < sz ; n++){
if(sz % 2 == 0){ // even
if(str[n] == 'L'){
sum += n;
if(n < sz / 2) changeVal.push_back(sz - 1 - n * 2); // n < sz / 2
else changeVal.push_back(0); // sz / 2 <= n
}
else{ // R
sum += sz - 1 - n;
if(n < sz / 2) changeVal.push_back(0);
else changeVal.push_back(n * 2 - sz + 1); // sz / 2 <= n
}
}
else{ // odd
if(str[n] == 'L'){
sum += n;
if(n < sz / 2) changeVal.push_back(sz - 1 - n * 2); // n < sz / 2
else changeVal.push_back(0); // sz / 2 <= n
}
else{ // R
sum += sz - 1 - n;
if(n <= sz / 2) changeVal.push_back(0);
else changeVal.push_back(n * 2 - sz + 1); // sz / 2 <= n
}
}
}
sort(changeVal.begin(), changeVal.end());
for(int n = changeVal.size() - 1 ; n >= 0 ; n--){
sum += changeVal[n];
cout << sum << ' ';
//cout << changeVal[n] << ' ';
}
cout << endl;
}
return 0;
}