蓝桥杯 十一届C++A组 字符排序 21分（运行超时）

本文主要是介绍蓝桥杯 十一届C++A组 字符排序 21分（运行超时），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

1. 此题考查的冒泡排序中的交换次数，其实就是考察当前数与后面的逆序对个数问题。而为了最大利用位数，应当使每一位都不小于后面的字符，否则会造成一次逆序对的浪费（贪心，为了使总位数最少）。

2. 通过上面的思路，可以得知每一个不同长度的最大逆序对数量，一定是由严格递减的字符串组成。而如果要获得逆序对数量介于相邻长度之间的数只需要对逆序对数量较大的进行部分修改即可。

3. 修改采用dfs进行判断。

#include <bits/stdc++.h>
using namespace std;
int i=2;int a;
int ans[1000];
bool check()
{int sum=0;int pre = 0,cnt = 1;for(int j=2;j<=i;j++){if(ans[j] == pre){cnt++;sum+=j-cnt;}else{pre = ans[j];cnt = 1;sum+=j-1;}}
//	for(int j = i;j>=1;j--)
//		{
//			cout<<(char)(ans[j]+'a');
//		}cout<<"           "<<sum<<endl;if(sum == a){for(int j = i;j>=1;j--){cout<<(char)(ans[j]+'a');}return true;}else{return false;}
}bool dfs(int pos,int most)
{if(pos == 1){return check();}for(int j = 0;j<=most;j++){ans[pos] = j;if(dfs(pos-1,max(0,j))) return true;}return false;
}
int main()
{cin>>a;int num[1000] = {0};//可以先输出试探范围 for(;i<999;i++){num[i] = num[i-1]+i-1;if(a<=num[i]) break;}dfs(i,i-1);return 0;
}

这篇关于蓝桥杯 十一届C++A组 字符排序 21分（运行超时）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---