CocktailWithSwap

NC222152. CocktailWithSwap

描述

Mr. Cocktail get a string contain ${N}$ characters. The character in the string from left to right respective marked as $a_1, a_2 ... a_n$ . This string consists of lowercase letters only.

Cocktail can perform unlimited times exchange operations on this string. Each operation can choose two digits ${i,j}$ , satisfying $l \leq |i-j| \leq r$ , and exchange the letters in these two positions----That is, $a_i, a_j$ .
Cocktail hopes that the lexicographical order of this string after several exchanges is the smallest. Now given this string and ${l, r}$ , please output a string representing the smallest lexicographical order that Cocktail can achieve after several operations.

输入描述

In the first line, input three integer, indicating , the meaning is shown in the statement. 

The next line input a string  of length .Represents the initial string.

输出描述

Output a string representing the smallest lexicographical string reached after several operations with follow the rules as statement describe.

示例1

输入:

5 1 1
edcba

输出:

abcde

示例2

输入:

5 4 4
edcba

输出:

adcbe

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 12ms, 内存消耗: 912K, 提交时间: 2021-05-22 17:23:37

#include <bits/stdc++.h>
using namespace std;
int main(){
	string str, ans;
	int n, l, r;
	cin >> n >> l >> r;
	cin >> str;
	if(l == r){
		string tmp[l];
		for(int i = 0; i < n; i++){
			tmp[i%l] += str[i];
		}
		for(int i = 0; i < l; i++)
			sort(tmp[i].begin(), tmp[i].end());
		for(int i = 0; i <= n / l; i++){
			for(int j = 0; j < l; j++){
				if(i >= tmp[j].size())	continue;
				ans += tmp[j][i];
			}
		}
		cout << ans << endl;
	}else if(n >= l * 2){
		sort(str.begin(), str.end());
		cout << str << endl;
	}else{
		string tmp;
		for(int i = 0; i < n; i++){
			if(i < n - l || i >= n - (n - l))
				tmp += str[i];
		}
		sort(tmp.begin(), tmp.end());
		int cnt = 0;
		for(int i = 0; i < n; i++){
			if(i < n - l || i >= n - (n - l))
				str[i] = tmp[cnt++];
		}
		cout << str << endl;
	}
}