Link Sub: http://www.spoj.com/PTIT/problems/P17QPROB/
Người Gửi: Dương Lee
- Problem:
Cho M xâu kí tự. Nhiệm vụ của bạn là hãy ghép các xâu này thành một từ, sao cho từ thu được có thứ tự từ điển nhỏ nhất.Input
Dòng đầu tiên là số lượng bộ test T (T ≤ 100).
Mỗi test gồm số nguyên M (M ≤ 9) là số lượng các từ, theo sau là M xâu.
Mỗi xâu có độ dài không vượt quá 10.
Output
Với mỗi test hãy in ra xâu có thứ tự từ điển nhỏ nhất tìm được.
Example:
Với mỗi test hãy in ra xâu có thứ tự từ điển nhỏ nhất tìm được.
Input
5
4 acm ptit for students
5 k duz q rc lvraw
3 a bb cc
5 asf asfi asfi afsi okj
5 ukuy hopji lie jaa dcyi
Output:
acmforptitstudents
duzklvrawqrc
abbcc
afsiasfasfiasfiokj
dcyihopjijaalieukuy
- Solution:
Bài này sort theo 2 cặp xâu một. Xét 2 trường hợp ghép xâu: xau1xau2 hoặc xau2xau1
- Nếu xau1xau2 < xau2xau1 thì có nghĩa cặp hiện tại thỏa mãn
- Nếu xau1xau2 > xau2xau1 có nghĩa là cần đổi chỗ xau1xau2 -> xau2xau1
sort trong thư viện là heapsort.
- Code:
C++:
https://ideone.com/h4M0hN
#include <iostream>
#include <algorithm>
using namespace std;
struct data {
string a;
};
int cmp (data a, data b) {
if ((a.a+b.a)<(b.a+a.a)) return 1;
else return 0;
}
main () {
int t;
cin>>t;
int m;
struct data ma[15];
for (int i=1; i<=t; i++) {
cin>>m;
for (int j=1; j<=m; j++) {
cin>>ma[j].a;
}
sort (ma+1, ma+m+1, cmp);
string in="";
for (int j=1; j<=m; j++) {
in+=ma[j].a;
}
cout<<in<<endl;
}
}