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

#1

em có 1 bài như sau, mà nói chung là như ảnh, không biết em có hiểu sai đề không mà nó cứ bị sai test, ai giúp em với, đã 3 ngày rồi :frowning:

Capture
Capture.PNG1560×811 58.8 KB

còn đây là code em http://codepad.org/BGJXtpGD

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    int size, num;
    vector<int> arr;
    vector<int> digit;
    int temp = 0, count = 0;
    cin >> size;
    while (temp < size)
    {
        cin >> num;
        arr.push_back(num);
        temp++;
    }
    for (int i = 0; i < arr.size(); i++)
    {
        if (arr[i] > 9)
        {
            while (arr[i] > 0)
            {
                digit.push_back(arr[i]%10);
                arr[i] = arr[i] / 10;
                count++;
            }
        }
        else {
            digit.push_back(arr[i]);
            count++;
        }
    }
    sort(digit.begin(),digit.end(),greater<int>());
    double final=0;
    int numb=digit.size();
    for(int i=0;i<digit.size();i++)
    {
        final+=(digit[i]*pow(10,numb-1));
        numb--;
    }
    cout<<final;

}

cảm ơn mọi người ạ

#2

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

#3

ý tưởng , lấy chữ số đầu tiền của từng số so sánh thằng nào lớn thì cho vào trước , nếu chữ số dầu tiền == nhau thì so sánh số tiếp theo, lặp lại nhu trên đến hết la xong

#4

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 @@

#5

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

2 Likes
#6

Đọ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);
2 Likes
#7

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

#8

“745” = “7” + “45” :slight_smile:

1 Like
#9

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 :frowning:
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 */
    }
}
#10

Để ý 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 :slight_smile: nó chạy rất nhiều lần muh.

1 Like
#11

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 ạ.

#12

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.

#13

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

#14

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.

1 Like
#15

Đừ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.

1 Like
#16

Đâ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

#17

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;
}
1 Like
#18

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 này viết theo thuật toán đề cho trước, nên rất có thể là comparator sai.

1 Like
#19

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.

Ghi chú

Nếu để <= luôn thì sẽ sai (vd. a = “11”, b = “1”).
Với lại còn thiếu cái dãy đó là max luôn, swap thì chắc chắn là không được (“47” vs “4”: “4794” vs. “4947”).

2 Likes
#20

Đâ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

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?