交换问题

Question

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

Given a number N. You have to perform exactly two swap operations to make the number as large as possible.

You are given a number N (10 ≤ N ≤ 2×10⁹). You have to perform exactly two swap operation. You may choose any two unequal positions of this number, and swap the digits at those two positions.

Like, for number 451 you can choose position 1 and 2 then swap this after swapping number will 541 again you can choose position 2 and 3 and swap after swapping number become 514.

What is the largest number you can get after these two operations?

所以我编写了一个有意义的代码，但我不明白为什么在我的代码中 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] 字符的 copy。要在这两个字符之间实际切换，您需要使用临时变量来存储 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

交换问题

Problems with swapping

c++

algorithm

swap