思路:
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;
}