2022.04.04蓝桥杯第十一届 10.字串排序（逆序对）

试题J 字串排序

• 【问题描述】
  小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。
  

  
  

  
  在冒泡排序中，每次只能交换相邻的两个元素。
  

  
  

  小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
  

  
  

  
  例如，对于字符串 lan 排序，只需要 1 次交换。
  

  
  

  对于字符串 qiao 排序，总共需要 4 次交换。
  

  
  

  
  小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 V 次交换，可是他忘了把这个字符串记下来，现在找不到了。
  

  
  

  
  请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 V 次交换。
  

  
  

  如果可能找到多个，请告诉小蓝最短的那个。
  

  
  

  如果最短的仍然有多个，请告诉小蓝字典序最小的那个。
  

  
  

  请注意字符串中可以包含相同的字符。
  

  
  

• 【输入格式】
  输入的第一行包含一个整数V，小蓝的幸运数字。
  

  
  

• 【输出格式】
  题面要求的一行字符串。
  

  
  

【样例输入】
4
【样例输出】
bbaa
【样例输入】
100
【样例输出】
jihgfeeddccbbaa
【评测用例规模与约定】
对于 30% 的评测用例， 1 ≤ V ≤ 20。

对于 50% 的评测用例， 1 ≤ V ≤ 100。

对于所有评测用例， 1 ≤ V ≤ 10000。

参考原文

• 分析
  思路：把这题拆成两个部分，第一个部分是确定最小长度，第二个部分是确定最小字符序

---

一、
求能交换次数V的字符串的最小长度，也就是求长度为多少时，能交换次数大于等于V次
给出一个定义：交换的次数等于字符串的逆序对个数
例如ba，b比a大，逆序对个数是1，cba，b产生1个，a产生两个，逆序对是3。

于是很自然想到，在长度相同的情况下，逆序数越多，交换次数越多。

为了保证逆序对尽可能的多，我们构造的字符串尽量是递减序列。

例如：
长度 len = 1时，我们构造的字符串要形如 a，逆序对个数为 0，交换次数为 0。

当长度 len = 2 时，我们构造的字符串要形如 ba，逆序对个数 1，交换次数为 1。

当长度 len=3 时，我们构造的字符串要形如 cba，逆序对个数为 3，交换次数为 3。

⋯
当长度 len=26时，我们构造的字符串得为 zyxwvutsrqponmlkjihgfedcba，逆序对个数为 325，交换次数为 325。

题目中的要求是V最大是10000，所以这个325是远远达不到要求的，所以势必有字符是要重复的。

• 那接下来我们考虑一个新的问题，在只有a,b,c的情况下，构造出一个长度为7，交换次数最多的字符串，怎么想呢？给定一个字符串，插入一个字符，针对每个插入的字符而言逆序对增加的个数=前面比该字符大的字符数量 + 后面比该字符小的字符数量。
  

  
  

  
  每次我们只要插入当前字符串中字符个数最少的字符就好了
  为什么呢？
  因为字符串中字符个数最少的这个字符与它前面和后面的字符都构成逆序对，它本身个数少，说明其他字符多，那构成的逆序对个数也多
  比如cbaa,插入个数少的b变成cbbaa,增加了1+2个逆序对
  而如果插入的是a，变成cbaaa，只增加了2个逆序对
  所以我们对于上面的问题，长度为7，有三种方案cccbbaa,ccbbbaa,ccbbaaa，字符序最小的话，当然是ccbbaaa了。
  

  
  

• 不过我们原来的问题是：在给定的长度为len的字符串，其最大逆序数个数是多少？为什么要求这个呢，因为当我们找到第一个长度len，其最大逆序数>=V时，我们就可以从这个长度产生字符序最小的字符串，而这个len也就是最小的长度。
  

  
  

• 那回到正题，有了上边的例子，我们明白了，一个长度为len的字符串里边，要达到最大逆序数，字符之间要逆序，每个字符个数最好是平均分配的，又要字符序最小，个数多的应该是字符顺序小的。
  

  
  

  字符数量为len/26+1(向下取整)的字符有len%26​个，字符数量为len/26的字符有26-len%26个。
  

  
  

  那给定len，最大的交换次数的公式如下所示：
  
  这个公式是分为两部分，即字母个数较少的字母构成的逆序对，和相比较字母个数多1的字母构成的逆序对，什么叫相比较字母个数多1？比如ccbbaaa，a就变比b和c的个数2多了1了。
  

  
  

  最多只会多1个，因为要尽可能地均匀,越均匀逆序对个数越大，比如说len=7时，gfedcba就比ccbbaaa的逆序对个数多(上面举的例子ccbbaaa限定了只能填abc这三个字母，所以和题目实际不同，只是作为假设。
  

  
  

  其实对于长度不超过26的字符串来说，它们是不可能有字母个数相比较多1的字母，直接按照逆序一个一个地排就好了，直到长度为27，才有zyx…cbaa,a多一个的情况)
  先不看分母的除以2，分子部分其实是针对每一个字母的，就是只看这个字母前面比它大的和它构成逆序对，后面比它小的也构成逆序对
  那这样算的话，会有重复
  比如说长度为55的字符串zzyyxx…eeddcccbbbaaa
  在单独看某一个y的时候，算了y和某一个x是一对逆序对，在单独看那一个x时候又会算y和x构成的这对逆序对
  所以是两两之间会重复计算，所以要除以2
  再来看看分子的两部分

• +左边的是相比较字母个数多1的字母构成的逆序对，也就是例子中的cccbbbaaa这一部分，每个字母其实都和除自己这个字母以外的所有其他字母构成逆序对
  (len-(len/26+1))->(55-(55/26+1))=(55-3)=52，除自己这个字母以外，和剩下的所有其他字母构成逆序对，比如a就和zzyyxx…eeddcccbbb构成逆序对，就是减去a本身的3个a,剩下的数
  (len/26+1)->(55/26+1)=3,相比较字母个数多1的字母它自己的个数，比如cba每个都有3个
  (len%26)->(55%26)=3,相比较字母个数多1的字母有几个，a,b,c这有3个字母
  它们相乘就是相比较字母个数多1的字母构成的逆序对个数
• +右边的是字母个数较少的字母构成的逆序对，也就是例子中zzyyxx…eedd这一部分，每个字母也都和除自己这个字母以外的所有其他字母构成逆序对
  (len-(len/26))->(55-(55/26))=53,每个字符，和除自己这个字母以外的其他所有字母都构成逆序对比如z就和除zz以外的剩下53个字母都构成逆序对
  (len/26)->(55/26)=2,不多余重复的字母的个数，即zzyyxx…eedd，zyx…ed每个字母都有2个
  (26-len%26)->(26-55%26)=(26-3)=23，这是不多余重复的字母个数，即zyx…ed这23个字母
  它们相乘就是字母个数较少的字母构成的逆序对个数
• 按照这个计算方法，就能计算出至少多长的字符串长度能构成V个逆序对个数

---

二、
确定如何放字母能得到最小字符序
在已经的到的len长度，从前往后依次放字母，每个位置都尝试把a-z这26个字母放进去试试
如果当前位置能放字母j，就确定这个位置放j，然后继续尝试放下一个位置
怎么判断当前位置能不能放j?
在当前位置放j后，预测一下后面的放法，如果后面有放法能使得最后所有的逆序对个数大于等于V，说明这个位置可以放j

#include
using namespace std;
int V , len , now , cnt[27] , sum[27];
int get_max(int len){
    return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
bool check(int x , int n){//当前位置i放x字母后，后面的n个位置是否符合要求 
    memset(cnt , 0 , sizeof(cnt));//cnt记录后面n个位置放置的对应字符数量
    int add1 = 0 , add2 = 0;
    for(int j = 26 ; j >= x + 1 ; j --) add1 += sum[j];//1~i-1里边比当前插入字符大的字符数量
    sum[x] ++ ;//当前字符数量增加1
    for(int L = 1 ; L <= n ; L ++){//当前位置i放了x,看当前位置i后面剩下的n个位置能不能放好字母使得达到V的条件，这是一个预测过程 
        //ma保存i位置后面的n个位置能增加的最大逆序对个数 L-1-cnt[j]+num
        //L-1-cnt[j]是当前字符之后的比当前字符小的字符数量的最大值
        //num是1~pos+L-1前的比当前放置字符字典序大的字符数量
        int ma = -1 , pos = 0 , num = 0;
        for(int j = 26 ; j >= 1 ; j --){//枚举i位置后面的n个位置，每个位置放什么字母 
            if(L - 1 - cnt[j] + num > ma){//L - 1是算i+1到i+L的个数(不算i+L自己) 
			// - cnt[j] 如果在i+1到当前位置i+L前有放过字母j，然后当前位置i+L也尝试放j，
			//那当前位置不和前面放j的位置构成逆序对 要减掉前面放j的位置个数 
                ma = L - 1 - cnt[j] + num;
                pos = j;//在L这个位置放上字母j 
            }
            num += sum[j];//num是从1-i位置里大于等于j的数的个数 
			//因为j是从26逆着放到1的 到下一轮循环时，j--假设记为j'，那要求的1-i里比j'大的数就是num 
			//那么这个j'会和前面已经确定好的所有属于26~(j'+1)的数构成逆序对
			//其实最后的num是算的所有大于等于1的个数，但是没关系，它不会更新到ma里 
        }
        add2 += ma , cnt[pos] ++;//L这个位置确定下来，放pos这个字母 
    }
    if(now + add1 + add2 >= V) {//now是i这个位置以前的所有逆序对个数,
	//add1是i位置放进x后,x与前面所有字母构成的逆序对 
	//add2是i位置放进x后，后面的位置的所有数能增加的逆序对个数，分为2部分，
	//1、后面位置所有的数与1~i部分的数构成的逆序对个数
	//2、后面所有位置L，分别与从i+1~i+L-1之间的数构成的逆序对个数，然后这些逆序对的和 
        now += add1;//now更新i位置确定好放字母x后，从1~i位置所有逆序对个数 
        return true;
    }
    else {//i这个位置放x不能使逆序对个数>=V 
        sum[x] -- ;
        return false;
    }
}
signed main()
{
    string ans = "";
    cin >> V;
    for(int i = 1 ; ; i ++) {
        if(get_max(i) >= V){//i这个长度的字符串最多能有get_max(i)个逆序对 如果get_max(i) >= V，
		//那么i这个长度就是我们需要的最短长度 
            len = i;
            break ;
        }
    }
    for(int i = 1 ; i <= len ; i ++){//按长度从左往右尝试放字母 
        for(int j = 1 ; j <= 26 ; j ++){//按顺序'a'-'z' 26个字母放   先用1-26代表这26个字母 
            if(check(j , len - i)){//现在是在第i位放j字母  看i后面的len-i个字母能否符合条件 
                ans += char(j + 'a' - 1);//符合条件就把j放在i这个位置 
                break ;//然后尝试放下一个位置 
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

main里面放字母是从1~26的顺序，是为了确保字典序最小
比如说V=3，如果从1->26的顺序放就会是cba，如果是26->1的顺序就是zyx
而后面check放字母是按26~1的顺序,是为了让num里面存的都是1->i里比当前要放的字母大的字母个数

纯享版

#include
using namespace std;
int V,len,now;
int sum[27];
int get_max(int len){
	return ((len-(len/26+1))*(len/26+1)*(len%26)+(len-len/26)*(len/26)*(26-len%26))/2;
}
bool check(int x,int n){
	int add1=0,add2=0;
	for(int j=26;j>x;--j) add1+=sum[j];
	sum[x]++;
	int cnt[27]={0};
	for(int L=1;L<=n;++L){
		int ma=-1,num=0,pos=0;
		for(int j=26;j>=1;--j){
			if(L-1-cnt[j]+num>ma){
				ma=L-1-cnt[j]+num;
				pos=j;
			}
			num+=sum[j];
		}
		add2+=ma;
		cnt[pos]++;
	}
	if(add1+add2+now>=V){
		now+=add1;
		return true;
	}
	else{
		sum[x]--;
		return false;
	}
}
int main(){
	cin>>V;
	for(int i=1;;++i){
		if(get_max(i)>=V){
			len=i;
			break;
		}
	}
	string s="";
	for(int i=1;i<=len;++i){
		for(int j=1;j<=26;++j){
			if(check(j,len-i)){
				s+=char(j+'a'-1);
				break;
			}
		}
	}
	cout<<s<<endl;
}

注释版

#include
using namespace std;
int V , len , now , cnt[27] , sum[27];
int get_max(int len){
    return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
	//如果长度不到26  后面那一项里len/26=0，后面那一项为0 
}
bool check(int x , int n){//当前位置i放x字母后，后面的n个位置是否符合要求 
    memset(cnt , 0 , sizeof(cnt));//cnt记录后面n个位置放置的对应字符数量
    int add1 = 0 , add2 = 0;
    for(int j = 26 ; j >= x + 1 ; j --) add1 += sum[j];//1~i-1里边比当前插入字符大的字符数量
    sum[x] ++ ;//当前字符数量增加1
    for(int L = 1 ; L <= n ; L ++){//当前位置i放了x,看当前位置i后面剩下的n个位置能不能放好字母使得达到V的条件，这是一个预测过程 
        //ma保存i位置后面的n个位置能增加的最大逆序对个数 L-1-cnt[j]+num
        //L-1-cnt[j]是i+1~i+L-1范围内的字母比当前位置L的字母大的字符数量值，也就是 i+1~i+L-1区间内字母和L构成的逆序对个数 
        //num是1~pos+L-1前的比当前放置字符字典序大的字符数量
        int ma = -1 , pos = 0 , num = 0;
        for(int j = 26 ; j >= 1 ; j --){//枚举i位置后面的n个位置，每个位置放什么字母 
            if(L - 1 - cnt[j] + num > ma){//L - 1是算i+1到i+L的个数(不算i+L自己) 
			// - cnt[j] 如果在i+1到当前位置i+L前有放过字母j，然后当前位置i+L也尝试放j，
			//那当前位置不和前面放j的位置构成逆序对 要减掉前面放j的位置个数 
			//i+1到i+L-1的字母一定是逆序排序的，因为这样排得到的ma最大 不会出现azz这种情况 
			// 那么当L这个位置放j的时候，直接减cnt[j]就好了，比如zzyxx,后面的x是L位置,那就减cnt[x]，即减1
			//因为前面的zzy都会和x构成逆序对 
                ma = L - 1 - cnt[j] + num;
                pos = j;//在L这个位置放上字母j 
            }
            num += sum[j];//num是从1-i位置里大于等于j的数的个数 
			//因为j是从26逆着放到1的 到下一轮循环时，j--假设记为j'，那要求的1-i里比j'大的数就是num 
			//那么这个j'会和前面已经确定好的所有属于26~(j'+1)的数构成逆序对
        }
        add2 += ma , cnt[pos] ++;//L这个位置确定下来，放pos这个字母 
    }
    if(now + add1 + add2 >= V) {//now是i这个位置以前的所有逆序对个数,
	//add1是i位置放进x后,x与前面所有字母构成的逆序对 
	//add2是i位置放进x后，后面的位置的所有数能增加的逆序对个数，分为2部分，
	//1、后面位置所有的数与1~i部分的数构成的逆序对个数
	//2、后面所有位置L，分别与从i+1~i+L-1之间的数构成的逆序对个数，然后这些逆序对的和 
        now += add1;//now更新i位置确定好放字母x后，从1~i位置所有逆序对个数 
        return true;
    }
    else {//i这个位置放x不能使逆序对个数>=V 
        sum[x] -- ;
        return false;
    }
}
signed main()
{
    string ans = "";
    cin >> V;
    for(int i = 1 ; ; i ++) {
        if(get_max(i) >= V){//i这个长度的字符串最多能有get_max(i)个逆序对 如果get_max(i) >= V，
		//那么i这个长度就是我们需要的最短长度 
            len = i;
            break ;
        }
    }
    for(int i = 1 ; i <= len ; i ++){//按长度从左往右尝试放字母 
        for(int j = 1 ; j <= 26 ; j ++){//按顺序'a'-'z' 26个字母放   先用1-26代表这26个字母 
            if(check(j , len - i)){//现在是在第i位放j字母  看i后面的len-i个字母能否符合条件 
                ans += char(j + 'a' - 1);//符合条件就把j放在i这个位置 
                break ;//然后尝试放下一个位置 
            }
        }
    }
    cout << ans << '\n';
    return 0;
}