Link Sub: http://www.spoj.com/PTIT/problems/P173PROG/
Người Gửi: Dương Lee
- Problem:
Cho 1 xâu kí tự s, hãy sắp xếp lại vị trí của các kí tự trong xâu để được một xâu p mới thoả mãn thứ tự từ điển của p lớn hơn thứ tự từ điển của s. Trong trường hợp có nhiều đáp án, tìm kết quả có thứ tự từ điển nhỏ nhất.
Input
Dòng đầu tiên gồm 1 số nguyên dương t – số lượng test (t < 100 001).
t dòng tiếp theo mỗi dòng chứa 1 xâu kí tự s
(0 < |s| < 101, xâu kí tự chỉ gồm các chữ cái tiếng Anh viết thường).
t dòng tiếp theo mỗi dòng chứa 1 xâu kí tự s
(0 < |s| < 101, xâu kí tự chỉ gồm các chữ cái tiếng Anh viết thường).
Output
Example:
Với mỗi test, in ra 1 dòng là xâu kí tự p có thứ tự từ điển lớn hơn xâu s. Nếu không có kết quả, in ra "BIGGEST" (không có dấu ngoặc kép).
Input
4
ccd
tv
wolf
fnf
Output:
cdc
vt
BIGGEST
nff
- Solution:
Bài này thực chất là sinh hoán vị kết tiếp. Nếu không sinh tiếp được thì đó là xâu lớn nhất.
- Code:
C++:
https://ideone.com/eSi8n0
#include <iostream>
using namespace std;
string HV_kt (string s)
{
int n = s.length();
int i = n - 1 - 1;
while (i>=0 && s[i]>=s[i+1]) i--;
if (i>=0)
{
int vt;
for (int j = n-1; j>=0; j--)
if (s[j]>s[i])
{
vt = j;
break;
}
char tmp = s[vt];
s[vt] = s[i];
s[i] = tmp;
int l = i+1, r=n-1;
while (l<=r)
{
tmp = s[l];
s[l] = s[r];
s[r] = tmp;
l++;
r--;
}
return s;
}
return "BIGGEST";
}
int main ()
{
int t;
cin>>t;
string s;
while (1)
{
if (t==0) break;
t--;
cin>>s;
cout<<HV_kt (s)<<endl;
}
return 0;
}JAVA:
...Python:
...