Sắp xếp dãy số để nối lại thành số nguyên lớn nhất

em sửa code them setprecision để nó ra số lớn, mà cũng không đúng

em cho ra số ra 1 array rồi sort lại, sau đó in ra, nhưng không hiểu sao lại sai @@

Nhìn chỗ comparator là biết sai oài bạn viết comparator rồi thảy vào, xài default ko ra đúng đâu.

Đọc gợi ý là hiểu thôi mà. Xử lý ở dạng chuỗi (string)
viết lại comparator cho string theo gợi ý của đề bài:

bool cmp_greater(const string &a,const string &b) {
    return (a+b) > (b+a); // ab>ba
}

...
sort(x.begin(),x.end(),cmp_greater);

em thắc mắc là đề này 45 7 thì kq sẽ là 745 hay sẽ là 754 ạ?

“745” = “7” + “45”

mọi người ơi, em viết lại code theo hướng dẫn mà vẫn sai ,mọi người giúp em với
code em http://codepad.org/ILQ4PY14

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
using namespace std;
bool check(int a, int b)
{
    ostringstream o1;
    ostringstream o2;
    o1 << a << b; //4 56 thi 456
    o2 << b << a; //4 56 thi 564
    istringstream i1(o1.str());
    istringstream i2(o2.str());
    int x1, x2;
    i1 >> x1; //456
    i2 >> x2; //564
    if (x1 < x2) return true;
    return false;
}
int main()
{
    vector<int> x1;
    int n,count=0,x;
    cin>>n;
    while(count<n)
    {
        cin>>x;
        x1.push_back(x);
        count++;
    }
    for (int i = 0; i <x1.size()-1; ++i)
    {
        for (int j = i+1; j <x1.size(); ++j)
        {
            if(check(x1[i],x1[j])==true)
            {
                swap(x1[i],x1[j]);
            }
        }
        /* code */555
        
    }
    for (int i = 0; i <x1.size() ; ++i)
    {
        cout<<x1[i];
        /* code */
    }
}

Để ý rằng số nguyên tới 10^9 => ghép lại phải 64 bit mới tính đúng. Đoạn ghép số thì mình sẽ viết bằng C nó chạy rất nhiều lần muh.

Là sao ạ? E đang học cấu trúc dữ liệu giải thuật bằng c++ . E chưa hiểu cái 64bit a nói lắm nó nghĩa là sao ạ.

mình nghĩ bài này bạn nên viết thêm hai hàm, 1 hàm chuyển tham số kiểu int truyền vào thành kiểu String trả về, một hàm thì làm ngc lại.

String IntToString(int n);
int StringToInt (String str);

vd: n = 123; chuyển thành String str = “123”;

Còn lại là bạn so sánh các String rồi xuất ra màn hình theo thứ tự là được. Nếu đề yêu cầu xuất ra số thì bạn gọp các String lại, rồi chuyển sang int là được.

Em làm như thế ở code dưới a. Nhưng không đc

Code của bạn sai logic rồi, chỗ hàm check bạn so sánh 2 số, xong rồi bạn coi thằng nào lớn hơn rồi bạn ghép nó lại, như vậy đâu có được.

Bạn phải so sánh toàn bộ rồi tìm thằng lớn nhất ghép vs thằng lớn thứ nhì chứ.

vd như trong code của bạn a=4, b=56 lỡ nó còn thằng c=50 nữa thì sao. Bạn check 2 thằng a vs b, rồi bạn ghép nó thành 564, lúc này bạn check tiếp c là sai rồi.

Đừng tách thành các số/chữ số, hãy áp thẳng function so sánh với string như @Gio đã comment ở trên.

Đâu có .em có gắn vào vòng for đó a. Nó sẽ xét hết dãy chứ. A cứ thử chạy đi là biết

Mình ko có chuyên về C++, vs lại bây h sao mà mình test được.
Mình làm theo ý mình nhé.

int main() {
    int n;
    scanf("%d",&n);
    int arr[n];
    for(); // lấy giá trị mảng vào
    String str[n];
    for(); // chuyển mảng thành mảng String;
    String result;
    for(); //xét từng giá trị tìm thằng lớn nhất đưa vào result, cho thằng lớn nhất trong mảng str[n] = null, xong rồi cứ duyệt n lần, cứ mỗi lần đưa thằng lớn nhất vào result;
}

2^32 hơn 4*10^9 một chút. Vậy không quá 10^9 tức là 30 bit. Chập hai số lại với nhau là 62 bit (chập lại chứ không phải nhân với nhau) , vậy dùng toàn số thì phải uint64_t.

Code của bạn sai logic rồi, chỗ hàm check bạn so sánh 2 số, xong rồi bạn coi thằng nào lớn hơn rồi bạn ghép nó lại, như vậy đâu có được.

Bạn phải so sánh toàn bộ rồi tìm thằng lớn nhất ghép vs thằng lớn thứ nhì chứ.

Code này viết theo thuật toán đề cho trước, nên rất có thể là comparator sai.

Tóm tắt (khá dễ nhưng hơi cực).

Với <= là thứ tự từ điển, đặt aRb := a + b < b + a với + là phép nối chuỗi
aQb := a[1..min(|a|, |b|)] <= b[1..min(|a|, |b|)] với |s| là độ dài của chuỗi s,
ta sẽ c/m R có tính chất thứ tự. Dễ thấy Q có tính bắc cầu.

Do |a + b| = |b + a| nên (a + b)Q(b + a). Lại có (a + a)Q(a + b) và (b + a)Q(b + b) nên (a + a)Q(b + b). Tương tự, nếu bRc thì (a + a)Q(c + c). Giờ ta phải tìm cách suy ngược về aRc. Chia ra 4 trường hợp ta suy ra đpcm. Vậy sắp xếp theo R là đúng.

Đây là số a ơi test đầu là 20 9 3 2 sẽ ra 93220 nhưng không phải ghép lại hay đổi vị trí lớn nhất

Mình xem nó là chuỗi cho tổng quát đề cho toàn là số thì sẽ không có chuỗi bựa như “0000…06”, và dù gì thì chuỗi dạng này cũng cực nhỏ (zero đầu).

p/s: có lẽ nên chuyển hướng qua a + a < b + b.

Hic em đã thử rất nhiều test nhueng vẫn sai. Không hiểu đề kiểu gì nữa