Tìm dãy hoán vị

#1

Cho p1,p2,…,pn là một hoán vị của (1,2,…,n). Ta viết các số p1,p2,…,pn rồi đặt các dấu “<” nếu pi < pi+1 hoặc “>” nếu pi > pi+1. Sau đó nguời ta xoá các số đó còn lại các dấu “<”, “>”. Yêu cầu tìm ra dãy hoán vị ban đầu thoả mãn dãy các dấu trên. Nếu có nhiều dãy thì in ra dãy hoán vị có thứ tự từ điển nhỏ nhất.
Ví dụ với dãy: <<>< ta có dãy 3 4 5 1 2 hoặc 1 2 4 3 5,… thì ta sẽ in ra dãy 1 2 4 3 5.
Yêu cầu: Cho xâu S là dãy các dấu (S có không quá 105 kí tự)
In ra dãy hoán vị thoả mãn.

INPUT: <<><
OUTPUT: 1 2 4 3 5

Mọi nguời cho em xin thuật toán bài này đuợc không? Với bộ dữ liệu 105 em không qua nổi ạ! Em cảm ơn!

#2

Lật ngược bài toán :smiley: đáp án phải có tính chất gì?

1 Like
#3

Là sao? Em không hiểu ý anh cho lắm! Nói rõ hơn cho em đuợc không ạ!

#4

dùng quay lui vét cạn thử được ko , dựa vào các dấu để xác định xem cấu hình sẽ có bao nhiêu phần tử , rồi mỗi phần tử ta lại sinh ra và thử , nhưng chắc được với n nhỏ chứ n lớn thì số lượng cấu hình quá lớn chạy ko nổi …@@

#5

Nếu làm như vậy sẽ chạy chỉ được một vài test thôi bạn ạ.
Bài này có sort đuợc ko mấy anh?

#6

Sort thì hỏng dữ liệu rồi bạn :smiley:

Ta đặt lại vấn đề: dãy nào nhỏ nhất có những nghịch thế liền kề ở những vị trí như vậy?

1 Like
#7

O(n): tạo 1 cái dslk a, 1 con trỏ p, và 1 số n, ban đầu n = 1, a có 1 số 1, con trỏ trỏ tới số 1 này. Với mỗi ký tự c trong S, nếu c là ‘<’ thì thêm ++n vào cuối a, rồi cho p trỏ tới phần tử vừa thêm vào này; nếu c là ‘>’ thì thêm ++n vào trước p, và cũng cho p trỏ tới phần tử vừa thêm vào.

minh họa cho dễ hiểu :V

S = <<><>>

bắt đầu
a = 1
    ^p

c = < : thêm 2 vào cuối a, p trỏ vào 2
a = 1 2
      ^p

c = < : thêm 3 vào cuối a, p trỏ vào 3
a = 1 2 3
        ^p

c = > : thêm 4 vào trước p, p trỏ vào 4
a = 1 2 4 3
        ^p

c = < : thêm 5 vào cuối a, p trỏ vào 5
a = 1 2 4 3 5
            ^p

c = > : thêm 6 vào trước p, p trỏ vào 6
a = 1 2 4 3 6 5
            ^p

c = > : thêm 7 vào trước p, p trỏ vào 7
a = 1 2 4 3 7 6 5
            ^p
Code C++:V 
std::string s;
std::cin >> s;
std::list<int> a{1};
auto p = begin(a);
for (char c : s) p = a.insert(c == '<' ? end(a) : p, a.size() + 1);
for (int x : a) std::cout << x << " ";
4 Likes
#9

Anh ơi, nếu làm như vậy thì làm sao đúng được ạ!
Ví dụ: >>>> thì phải in ra 5 4 3 2 1 …

Mà anh có thể viết đừng dùng vecto hay auto … em không hiểu ạ!

1 Like
#10

Như vầy chắc là ngon rồi.

// c++11
std::string s;
cin >> s;
s += '<'; // lính canh
std::vector<int> v(s.length());
std::iota(v.begin(), v.end(), 1);
bool flag = true;
auto len = s.length();
for(auto i=0, beg=0, tmp=0; i <= len; ++i) {
   if(s[i] == '>')
     if(flag) { flag = false, beg = i; }
   else
     if(!flag) { flag = true, tmp = i; while(beg < tmp) std::swap(v[beg++], v[tmp--]); }
}
3 Likes
#11

Anh ơi nếu như vậy liệu có đuợc đến 105 hay không ạ! Em ban đầu cũng làm gần như thế ạ!

#12

Để ý rằng mỗi kí tự chỉ đọc một lần, và mỗi ô nhớ trong mảng được đọc/ghi không quá hai lần.

3 Likes
#13

2 dòng được rồi :flushed:

s += '<';
std::vector<int> a(s.size());
std:iota(begin(a), end(a), 1);
// 2 dòng
for (size_t i = s.find('>'), j; i < s.size(); i = s.find('>', j))
    std::reverse(&a[i], &a[j = s.find('<', i)] + 1);

vậy hóa ra > là chỉ vị trí từ đâu tới đâu cần đảo ngược, < thì bỏ qua

edit: sửa lại tí bỏ cái begin(a) kia đi cho dễ nhìn hơn

2 Likes
#14

Nhưng nó là C++17 mà :smiley: và khó đọc vô cùng.

#15

C++11 luôn đó, có điều viết khó nhìn :rofl:

xài list 1 dòng ngắn hơn :flushed:

nếu viết dễ nhìn thì thế này:

for (size_t i = s.find('>'); i < s.size(); )
{
    size_t j = s.find('<', j);
    std::reverse(begin(a) + i, begin(a) + j + 1); // std::reverse(&a[i], &a[j] + 1); // bỏ begin(a)
    i = s.find('>', j);
}

6 dòng

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