Giải quyết bài toán ghép số để được số lớn nhất như thế nào?

binle · May 7, 2018, 3:01pm

Phong_Ky_Vo · May 6, 2018, 1:27pm

Hi dũng.
Cho các số 1, 3, 5, 7, 8, 9 viết số lơn nhất có 6 chữ số. @_@!

Phong_Ky_Vo · May 6, 2018, 2:22pm

Hi dũng.
Bài mày hay vậy sao lại xóa đi thế bạn ?

Chiều dài số ghép được là không đổi nên một số đứng trước đứng sau phụ thuộc vào chữ số đầu tiên của nó. Vậy nên ta luôn có 9xxx9xxxx9xx98xxx8xxxxx87xxxx7x7xxx7777xxx v.v.v.

P/S Đang nghĩ tiếp. ANh em có ý tường gì không ?

tntxtnt · May 6, 2018, 2:26pm

đọc vào dạng chữ rồi sắp xếp lớn tới bé rồi in ra ko có dấu cách ~.~

[“123”, “124”, “56”, “90”] -> [“90”, “56”, “124”, “123”] -> 9056124123

Phong_Ky_Vo · May 6, 2018, 2:29pm

Hi xn–tr-oja.
Vậy bộ test này [“8”, “89”, “87”] đâu xếp được ?? -> 89, 8, 87

tntxtnt · May 6, 2018, 3:10pm

vậy thì khi so sánh phải append thêm số đầu tiên vào cho bằng độ dài hết 8, 89, 87 -> 88, 89, 87 -> 89 88 87 -> 89 8 87

hên xui

vẫn còn vấn đề, ví dụ 43 < 434, nhưng 46 > 464 =), vậy với tie breaker xyzax và xyzbx là a < b, thôi cũng khó quá =)

edit: double độ dài là ổn:
vd:
43 434 46 464 46472 4647

max len = 5 -> chuyển thành chuỗi độ dài 10:
4343434343(43)
4344344344(434)
4646464646(46)
4644644644(464)
4647246472(46472)
4647464746(4647)

sort từ lớn tới bé:
4647464746(4647)
4647246472(46472)
4644644644(46)
4644644644(464)
4344344344(434)
4343434343(43)

Phong_Ky_Vo · May 6, 2018, 3:12pm

Hi xn–tr-oja.
Mình thấy ý tướng append là hợp lý.
Trường hợp chứ số đầu giống nhau là X ta so sánh chữ số thứ 2 Y nếu Y > X -> XYX > XXY vậy các số có chữ số thứ 2 lớn hơn số đầu xếp trước. Tường tự nếu Y < X thì xếp sau. Vấn đề nếu là XX và X khi só sánh chữ số thứ 3 với X là được.

tntxtnt · May 6, 2018, 3:20pm

có thể tạo 1 cái operator< theo kiểu a < b nếu ab < ba

8 < 89 nếu 889 < 898 (đúng) -> 89 sẽ đứng trước 8
8 < 87 nếu 887 < 878 (sai) -> 8 đứng trước 87

ko biết cái này với append cái nào lẹ hơn =)

edit: cái append là suy nghĩ theo lối mòn, cái a < b nếu ab < ba có lẽ đúng hơn

viết code cũng dễ hơn cái append kia nữa

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
    std::vector<std::string> p;
    for (std::string s; std::cin >> s; p.push_back(s));
    std::sort(begin(p), end(p), [](auto const& a, auto const& b){
        return a+b > b+a;
    });
    for (auto const& s : p) std::cout << s;
}

Phong_Ky_Vo · May 6, 2018, 3:19pm

Hi xn–tr-oja.
Theo mình thì dùng toán tử và chạy hàm xắp xếp có vẻ nhanh hơn vì thự tế append vào sẽ thừa.