Phoenix and Distribution(字典序贪心)

\(给定一串字母，分成k份，使得最大字典序最小。(字母可以任意组合)\)

\(------------------------------issue~------------------------\)

\(首先肯定先对字母排序，然后往k个盒子都丢一个字母(因为不能为空)\)

\(那么接下来，就一定能够要想清楚了......\)

\(\color{Red}Ⅰ.当接下来的字母都相等时，就均分到k个盒子里，因为这时候影响字典序的只是长度\)

\(\color{Purple}{Ⅱ.当接下来的字母不全相等，意味着什么?还能均分吗?}\)

\(问题的关键在于，接下去总会有不相等的字母，每次均分的话迟早轮到某个盒子分到的是较大的字母\)

\(那这样一定不会比我把所有字母接在第一个盒子更优，因为虽然我的长度长，但是相同位置上一定是最小的!!(字母已经排序了)\)

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+9;

char s[maxn];

string a[maxn],maxx;

int t,n,k,y,L;

void work()

{

	for(int i=1;i<=k;i++)

		a[i]+=s[++y];

}

int main()

{

	cin>>t;

	while(t--)

	{

		int flag=0;

		for(int i=1;i<=100000;i++)	a[i]="";

		cin>>n>>k>>(s+1);

		sort(s+1,s+1+strlen(s+1));

		L=strlen(s+1);

		for(int i=1;i<=k;i++)

			a[i]+=s[i];//先都分一个字典序最小的

		if(a[k]!=a[1])	cout<<a[k];//最大一定是a[k];

		else

		{

			int flag=1;

			for(int i=k+2;i<=L;i++)	if(s[i]!=s[i-1])	flag=0;

			if(flag)//都相等

			{

				y=k;

				while(y<n)	work();

				cout<<a[1];

			}

			else//不都相等

			{

				for(int i=k+1;i<=L;i++)	a[1]+=s[i];

				cout<<a[1];

			}

		}

		cout<<endl;

	}

}

巴特西

Phoenix and Distribution(字典序贪心)

最新文章

热门文章