交换问题

Question

我正在解决一个问题，问题描述是：

给定一个数字N。您必须执行两次交换操作以使数字尽可能大。

给你一个数字N(10≤N≤2×10⁹(。你必须准确地表演两个交换操作。你可以选择这个数字，并交换这两个位置的数字。

比如，对于451号，你可以选择位置1和2，然后交换这个交换号码后将541再次你可以选择位置2和3并且在交换号码变为514之后进行交换。

经过这两次操作后，你能得到的最大数字是多少？

所以我编写了一个有意义的代码，但我不明白为什么swap()在我的代码中交换相同的字符。您可以通过更好地查看代码来理解。

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--){
string s;
cin>>s;
ll k=2;//Number of minimum swaps
for(int i=0;i<s.size();i++){
char ma=s[i];//storing maximum number 
for(int j=i+1;j<s.size();j++){
if(ma < s[j]){
ma=s[j];
}
}
if(ma != s[i]){
swap(ma,s[i]);//swaping two chars if I found something bigger than s[i]. This line is also occuring error I mean unexpected behavior
k--;
}
cout<<"Iteration "<<i+1<<" "<<s<<endl;//This line is for inspecting what is going on
}
}
}

输入和输出：

Input:
1
123
Output:
Iteration 1 323
Iteration 2 333
Iteration 3 333

如果您看到代码，就不应该发生这种情况。

请说明swap的情况。

Answer 1

如@molbdnilo所述，ma变量只是s[j]字符的副本。要在这两个字符之间进行实际切换，需要使用一个临时变量来存储j的位置

int jtmp;
for(int j=i+1;j<s.size();j++)
{
if(ma < s[j])
{
ma=s[j]; jtmp = j;
}
} 

完整修改代码：

#include <iostream>
#include <string>
#define ll long long
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--){
string s;
cin>>s;
ll k=2;
for(int i=0;i<s.size();i++)
{
char ma=s[i]; int jtmp;
for(int j=i+1;j<s.size();j++)
{
if(ma < s[j])
{
ma=s[j]; jtmp = j;
}
}
if(ma != s[i])
{
swap(s[jtmp],s[i]);
k--;
}
cout<<"Iteration "<<i+1<<" "<<s<<endl;
}
}
}

结果：

1
45231
Iteration 1 54231
Iteration 2 54231
Iteration 3 54321
Iteration 4 54321
Iteration 5 54321

添加：您可以看到，在对字符串进行排序后，循环仍会持续一段时间。这可以通过一个检查字符串是否已排序的函数来解决。

#include <iostream>
#include <string>
#include <algorithm>
#define ll long long
using namespace std;
bool LF(char a, char b)
{
return a > b;
}
bool stringCheck(string x)
{
string y = x;
sort(y.begin(), y.end(), LF);
if (y == x) {return true;} return false;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--){
string s;
cin>>s;
ll k=2;
for(int i=0;i<s.size();i++)
{
char ma=s[i]; int jtmp;
for(int j=i+1;j<s.size();j++)
{
if(ma < s[j])
{
ma=s[j]; jtmp = j;
}
}
if(ma != s[i])
{
swap(s[jtmp],s[i]);
k--;
}
cout<<"Iteration "<<i+1<<" : "<<s<<endl;
if (stringCheck(s)) {break;}
}
}
}

结果：

1
45231
Iteration 1 : 54231
Iteration 2 : 54231
Iteration 3 : 54321