C. Phoenix and Distribution

Phoenix has a string s consisting of lowercase Latin letters. He wants to distribute all the letters of his string into k non-empty strings a1,a2,…,ak such that every letter of s goes to exactly one of the strings ai. The strings ai do not need to be substrings of s. Phoenix can distribute letters of s and rearrange the letters within each string ai however he wants.

For example, if s= abba and k=2, Phoenix may distribute the letters of his string in many ways, such as:

  • ba and ba
  • a and abb
  • ab and ab
  • aa and bb

But these ways are invalid:

  • baa and ba
  • b and ba
  • baba and empty string (ai should be non-empty)

Phoenix wants to distribute the letters of his string s into k strings a1,a2,…,ak to minimize the lexicographically maximum string among them, i. e. minimize max(a1,a2,…,ak). Help him find the optimal distribution and print the minimal possible value of max(a1,a2,…,ak).

String x is lexicographically less than string y if either x is a prefix of y and x≠y, or there exists an index i (1≤i≤min(|x|,|y|)) such that xi < yi and for every j (1≤j<i) xj=yj. Here |x|denotes the length of the string x.

题意： 将一组字符方程 k 份，使得字典序最大的一组最小。

可以观察到：

1、k 组的首字母应当最小，如果 k 组首字母有不同的。那么最大值就这个较大的字母，因为可以把其他所有字母加到别的组后面，并且不会比它大。

2、较大的字母应当放到末尾，且长度越大越好。

3、如果有两串字符相同，

  • 剩余未分配的字符相同，那么平均分到两组上面，是最优的
  • 剩余未分配的字符不相同，显然只分配给一组是最优的，因为可以使得较大的字母位置更靠后。

所以，可以这样贪心：

先从小到大排序，然后分配首字母，如果有不同的，直接输出最大的字母即可。

然后，后续分配只在当前所有字母加起来相等的组上分配，并且更新组数。

分配的时候，如果后续字母相同，则可以分配到各个相等的组上，否则只分配到第一组上。

最后，答案就是第一组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int MAX=100000+10;
int t,n,k,l,cnt;
char a[MAX];
vector<char> res[MAX];
int main(){
	//freopen("in","r",stdin);
	sf(t);
	while(t--){
		sf(n);sf(k);
		scanf("%s",a);
		l = strlen(a);
		sort(a,a+l);
		fi(i,0,k) res[i].clear();
		fi(i,0,k) res[i].pb(a[i]);
		if(res[k-1][0] != res[0][0]){
			putchar(res[k-1][0]);
			puts(""); continue;
			
		}
		int j = k,cnt=k;
		while(j<l){
			fi(i,0,cnt){
				if(j>=l) break;
				if(!i) res[i].pb(a[j++]);
				else {
					if(a[j] == a[j-1] && a[j] == a[l-1] ){
						res[i].pb(a[j]);
						j++;
					}else cnt = i;
				}
			}
		}
		fi(j,0,res[0].size()){
			putchar(res[0][j]);
		}
		pfc("\n");
	}
	return 0;
}