Cuộc diễu hành đường phố - LCOJ: Luyen Code Online

STPARA - Cuộc diễu hành đường phố

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Hàng năm, cứ vào dịp mùng ~2~ tháng ~9~, Sơn La lại tổ chức đoàn xe diễu hành. Đoàn xe gồm ~n~ xe đánh số từ ~1~ đến ~n~ diễu hành từ đường Trường Trinh đi về đường Chu Văn Thịnh. Khi đoàn xe đi vào đường Chu Văn Thịnh, tất cả các xe phải đi theo thứ tự (từ ~1~ đến ~n~). Khi đoàn xe tham gia diễu hành sẽ xếp hàng trên đoạn đường Trường Chinh và chưa có thứ tự theo yêu cầu. Để sắp xếp đúng thứ tự cho đoàn xe tiến vào đường Chu Văn Thịnh, ban tổ chức sử dụng đoạn đường Điện Biên để cho các xe tránh vào đó.

Trên các đoạn đường, các xe không được phép vượt nhau và không được đi lùi, chỉ duy nhất trên đoạn đường Điện Biên là các xe có thể quay đầu.

Bạn được ban tổ chức giao cho sắp xếp đoàn xe đi vào đường Chu Văn Thịnh theo đúng thứ tự, biết thứ tự các đoàn xe khi đi trên đường Trường Chình. Hãy lập chương trình để làm việc đó.

Input

Gồm nhiều bộ test, mỗi bộ test gồm ~2~ dòng:

Dòng đầu ghi số ~n~ là số xe tham gia diễu hành;
Dòng sau ghi ~n~ số nguyên dương là trật tự các xe trên đường Trường Chinh.
Kết thúc các bộ test là giá trị ~n = 0~

Giới hạn:

~1 ≤ n ≤ 10^5~;
Số test case không quá ~10~.

Output

Ứng với mỗi bộ test, ghi ra yes nếu có thể xếp đúng được thứ tự, ghi ra no nếu không thể.

Sample

Input #1

Output #1

yes
no

Hint

Ta bố trí các xe (trong test #1) tránh vào đường Điền Biên như hình dưới đây:

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.

khoihahaha đã bình luận lúc 10, Tháng 6, 2025, 11:34

Ý tưởng: dùng stack(st), một biến valid để theo dõi thứ tự sắp xếp từ 1..n

Duyệt mảng, nếu gặp phần tử arr[i] == valid(tức là đúng thứ tự) -> tăng valid lên
Ngược lại, đẩy vào stack để đợi.
Kiểm tra nếu !st.empty() && st.top() == valid -> tăng valid, st.pop()
Stack rỗng -> mảng có thể sắp xếp

CODE ĐÃ AC:

while (true)
{
    std::cin >> n;
    if (n == 0) break;
    for (int i = 0; i < n; i++) std::cin >> arr[i];
    std::stack<int> st;
    int valid = 1;
    for (int i = 0; i < n; i++)
    {
        while (!st.empty() && st.top() == valid)
        {
            valid++;
            st.pop();
        }
        if (arr[i] == valid) valid++;
        else st.push(arr[i]);
    }
    while (!st.empty() && st.top() == valid)
    {
        valid++;
        st.pop();
    }
    st.empty() ? std::cout << "yes\n" : std::cout << "no\n";
}
return 0;

Độ phức tap: O(n)

0

0988440189 đã bình luận lúc 20, Tháng 5, 2025, 8:27

ý tưởng cho bài này là các bạn tạoh thêm 1 thằng gia trị temp (sẽ kiểm tra thứ tự chuẩn đang cần ghép vào đít của những thằng đằng trước đã được sắp xếp chuẩn )- và tạo thêm 1 thằng ngăn xếp để đưa những thằng chưa hợp lí vào ngăn xếp để xét tiếp phần tử đằng sau trong mảng ( và ngăn xếp này luôn luôn là đơn điệu tăng (nghĩa là thằng trên luôn nhỏ hơn thằng dưới ) để tý sẽ có lúc phải lấy phần tử đỉnh trong ngăn xép ra ghép vào đuôi đoàn xe phía trước ) - duyệt toàn bộ mảng (i=1->n) , j bắt đầu từ giá trị 1: + Nếu ngăn xếp không rỗng và (a[i] đang lớn hơn đỉnh ngăn xếp )thì lấy thằng đỉnh ngăn xếp ra (nếu đỉnh đó thỏa mãn bằng j ) ghép vào đuôi ( cập nhật j tăng lên 1 đơn vị và nhớ xóa đỉnh ) => công việc này sẽ làm bằng vong lặp while (vì có thể có nhiều thằng trong ngăn xếp nhỏ hơn a[i] , nếu không thỏa mãn điều kiện đỉnh ngăn xếp = j thì trả về false luôn nhé ) + Nếu a[i]=j thì cập nhật j++ thôi + Nếu a[i]!=j thì đưa a[i] vào ngăn xếp ( lưu ý dấu cộng đầu tiên phải được thực hiện trước 2 dấu cộng sau *) => thoát ra khỏi vòng for duyệt mảng bạn cần xem xét nốt ngăn xếp bởi vì nó có thể không rỗng thì mình dùng while (cho đến khi rông) => kiểm tra đỉnh ngăn xếp với j hiện tại ( nhớ cập nhật ...) ====Ví dụ mảng {3,1,2,5,4} thì mình sẽ chứng minh mõm như sau : + B1 a[0]!=j (j=1) => cho 3 vào ngăn xếp và không thay đổi j => ngăn xếp hiện tại : st{3} + B2 a[1]=1=j (do j=1) => j++ và ngăn xếp hiện tại : st{3} + B3 a[2]=2=j (do j=2) => j++ và ngăn xếp hiện tại : st{3} + B4 a[3]=5 chạy vào vòng while do thỏa mãn (5>3) => lấy 3 ra kiểm tra (mà j đang bằng 3 => đúng ) , xóa đỉnh ngăn xếp và tăng j =>ngăn xếp rỗng và kết thúc vòng while => a[i]=5 !=j (j=4 cơ ) =>thêm vào ngăn xếp =>st hiện tại là {5} (đây là lí do của *lưu ý ... bên trên ) + B5 a[4]=4 =j =>j++ kết thúc for , chạy ra ngoài kiểm tra => các bạn tự nghĩ nốt bước này nhé Thankyou, Mu mãi đỉnh !!!!