Challenges in school №41

Link: Challenges in school №41

Description

There are n children, who study at the school №41. It is well-known that they are good mathematicians. Once at a break, they arranged a challenge for themselves. All children arranged in a row and turned heads either to the left or to the right.

Children can do the following: in one second several pairs of neighboring children who are looking at each other can simultaneously turn the head in the opposite direction. For instance, the one who was looking at the right neighbor turns left and vice versa for the second child. Moreover, every second at least one pair of neighboring children performs such action. They are going to finish when there is no pair of neighboring children who are looking at each other.

You are given the number n, the initial arrangement of children and the number k. You have to find a way for the children to act if they want to finish the process in exactly k seconds. More formally, for each of the k moves, you need to output the numbers of the children who turn left during this move.

For instance, for the configuration shown below and k=2 children can do the following steps:

At the beginning, two pairs make move: (1,2) and (3,4). After that, we receive the following configuration:

At the second move pair (2,3) makes the move. The final configuration is reached. Good job.

It is guaranteed that if the solution exists, it takes not more than "headturns".

Input
The first line of input contains two integers n and k (, ) — the number of children and required number of moves.

The next line contains a string of length n and consists only of characters L and R, where L means that the child looks to the left and R means that the child looks to the right.

Output
If there is no solution, print a single line with number −1.

Otherwise, output k lines. Each line has to start with a number () — the number of pairs of children, who turn at this move. After that print distinct integers — the numbers of the children who will turn left during this move.

After performing all "headturns", there can't be a pair of two neighboring children looking at each other.

If there are many solutions, print any of them.

Examples

input
2 1
RL
output
1 1
input
2 1
LR
output
-1
input
4 2
RLRL
output
2 1 3
1 2

Note
The first sample contains a pair of children who look at each other. After one move, they can finish the process.

In the second sample, children can't make any move. As a result, they can't end in k>0 moves.

The third configuration is described in the statement.

Problem solving

这道题的意思是有n个小朋友，初始的时候每个小朋友朝向的方向都会给出来。每一秒，你可以选择任意对且至少一对对着看的小朋友让他们看到反方向，即RL->LR。
问你在能否正好在k秒后，使得所有小朋友中不存在对着看的。不能的话输出-1。

因为将一对小朋友操作之后，可能会产生另一对对着看的小朋友，所以我们可以发现，总操作次数会有一个最大值和最小值。

  • 当你每一次操作都选出当前所有对着看的小朋友并让他们看向反方向的时候，这是最小值。
  • 当你每一次操作只选择一对小朋友让他们看向反方向的时候，这是最大值。

所以如果k在这个范围内，一定存在可行解。因为我们可以通过贪心调整每一次选择的小朋友的对数来达到k。
反之，输出-1。

所以我们可以首先求出最小值和最大值，然后构建答案。
构建的时候，先一个一个的放，当剩下的时间（k）与剩下的需要操作的最小次数相等时，按照最小的操作次数来进行输出。

Code

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 3e3+10;
vector<int> v[maxn];
char s[maxn];
int main()
{
    int n,k,minn=0,maxx=0;
    scanf("%d%d%s",&n,&k,s+1);
    while(1){
        minn++;
        int flag=0;
        for(int i=1;i<n;i++){
            if(s[i]=='R'&&s[i+1]=='L'){
                flag=1;
                v[minn].pb(i);
            }
        }
        if(!flag)   break;//如果已经没有可以操作的小朋友，退出循环
        for(auto pos:v[minn]){
            swap(s[pos],s[pos+1]);
        }
        maxx+=v[minn].size();
    }//minn最小值，maxn最大值
    if(k<minn-1||k>maxx){
        puts("-1");
        return 0;
    }
    for(int i=1;i<minn;i++){
        while(!v[i].empty()&&k>minn-i){
            printf("%d %d\n", 1, v[i].back());
            v[i].pop_back();
            k--;
        }//先一个一个放
        if(!v[i].empty()){
            printf("%d", v[i].size());
            for (auto it : v[i])
                printf(" %d", it);
            puts("");
            k--;
        }//然后按照最小的操作次数输出
    }
    return 0;
}
赏