CodeForces 1281B(思维+暴力）

Your friend Jeff Zebos has been trying to run his new online company, but it's not going very well. He's not getting a lot of sales on his website which he decided to call Azamon. His big problem, you think, is that he's not ranking high enough on the search engines. If only he could rename his products to have better names than his competitors, then he'll be at the top of the search results and will be a millionaire.

After doing some research, you find out that search engines only sort their results lexicographically. If your friend could rename his products to lexicographically smaller strings than his competitor's, then he'll be at the top of the rankings!

To make your strategy less obvious to his competitors, you decide to swap no more than two letters of the product names.

Please help Jeff to find improved names for his products that are lexicographically smaller than his competitor's!

Given the string

Note: String

There exists an integer

Input

The first line of input contains a single integer

Each test case consists of a single line containing two space-separated strings

It is guaranteed that the sum of

Output

For each test case, output a single line containing a single string, which is either

the new name which is obtained after swapping no more than one pair of characters that is strictly lexicographically smaller than
three dashes (the string "---" without quotes) if it is impossible.

Example

input

Copy

3
AZAMON APPLE
AZAMON AAAAAAAAAAALIBABA
APPLE BANANA

output

Copy

AMAZON
---
APPLE

Note

In the first test case, it is possible to swap the second and the fourth letters of the string and the resulting string "AMAZON" is lexicographically smaller than "APPLE".

It is impossible to improve the product's name in the second test case and satisfy all conditions.

In the third test case, it is possible not to swap a pair of characters. The name "APPLE" is lexicographically smaller than "BANANA". Note that there are other valid answers, e.g., "APPEL".

题意：T组测试数据，每组测试数据两个字符串a，c。最多只可以最多对a数组进行一个操作，即交换两个字符，使得a数组字典序大小严格小于c。如果存在这个结果，输出其中一个即可，否则输出---。

思路：wa了无数次思路错误。题意实际就是问，对一个字符串只进行1或者0次交换两个字符的操作，使得其字符串字典序最小，是多少？

将a赋值为b，对b进行排序，便利从头到尾，找到不相等的一个位置p，保存下来。再从后往前遍历a，倘若找到了这个被保存的数，变把这个数a[i]和a[p]交换，再判断字典序大小即可。。

几个测试数据

BAH BA

QA AQH

QABC AQBCH

QAB AQ

附AC代码

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <vector>
//const int maxn = 1e5+5;
#define ll long long
#define inf  0x3f3f3f3f
#define FOR(i,a,b) for( int i = a;i <= b;++i)
#define bug cout<<"--------------------------------------------"<<endl
 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int maxn = 100100;
using namespace std;
 string a,b,c;
int k,flag,len,hhh;
 
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a>>c;
        b = a;
        char temp = 1;
        sort(b.begin(),b.end());
        int pos = 0;
        for(int i = 0 ;i <a.length();++i)
        {
            if(a[i] != b[i])
            {
                temp = b[i];
                pos = i;
                break;
            }
        }
        for(int i = a.length()-1; i >= 0; --i)
        {
            if(temp == a[i]){
                char hhh = a[i];
                a[i] = a[pos];
                a[pos] = hhh;
            }
        }
        if(a < c) cout<<a<<endl;
        else cout<<"---"<<endl;
    }
 
}