SPOJ.COM - Thuật toán bài STPAR - Street Parade

Posted on October 28th, 2016

Đề bài:

Để đảm bảo rằng chiếc xe diễu hành sẽ hoạt động trở lại vào mùa hè, mỗi năm ban tổ chức quyết định một thứ tự xác định trước cho việc trang trí những chiếc xe. Kinh nghiệm dạy họ rằng nên giữ một cạnh trống để có thể đưa những chiếc xe vào theo đúng thứ tự.

Đường bên cạnh là rất nhỏ. Vì vậy, 2 chiếc xe không thể cùng vượt qua. Do đó, những chiếc xe nào vào sau sẽ phải ra trước. Bởi vì các xe đi rất gần nhau nên chúng không thể quay đầu hay vào trở lại. Bạn được cho thứ tự đến của những chiếc xe. Viết chương trình kiểm tra xem các chiếc xe có thể đi vào theo đúng thứ tự mà ban tổ chức quyết định hay không.

Đầu vào

Có nhiều test case. Dòng đầu tiên của mỗi test case là một số n, số lượng của những chiếc xe. Dòng thứ 2 chứa các số từ 1 đến n, sắp xếp theo tứ tự ngẫu nhiên. Tất cả các chữ số được phân cách bởi dấu cách. Những số này biểu diễn thứ tự, mà những chiếc xe đi đến con đường. Số xe là không lớn hơn 1000. Kết thúc của đầu vào là số 0.

Đầu ra

Với mỗi test case , in ra 1 dòng duy nhất là "yes" nếu như thoả mãn, ngược lại thì in ra là "no".

Ví dụ

Đầu vào:

5
5 1 2 4 3 
0

Đầu ra:

yes

Giải thích:

Ban đầu:

sptar-street-parade-spoj-com-thuattoan-phamvanlam-com-pic-1

Xe có thể thay đổi như sau:

sptar-street-parade-spoj-com-thuattoan-phamvanlam-com-pic-2

sptar-street-parade-spoj-com-thuattoan-phamvanlam-com-pic-3

sptar-street-parade-spoj-com-thuattoan-phamvanlam-com-pic-4

sptar-street-parade-spoj-com-thuattoan-phamvanlam-com-pic-5

Quá trình kết thúc.

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/STPAR/

Phân tích

Ở đây, mình sẽ dùng ngăn xếp stack để giải quyết bài toán. Bài toán này có thể xếp vào dạng sử dụng thuật toán tham lam Greedy.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

const int MAX = 1005;

int Order[MAX]; // Thứ tự ban đầu của những chiếc xe
int Stack[MAX]; // Biểu diễn ngăn xếp stack, tương ứng với đoạn đường bên cạnh
int St_size;    // Độ dài ngăn xếp
int Check;      // Lưu kết quả

int main()
{
	//freopen("input.txt","r",stdin);
	int N = 0;
	while(true)
	{
		// Nhập đầu vào là số lượng xe
		cin >> N;
		if(N == 0) break;

		for(int i = 0; i < N; i++)
			cin >> Order[i];
		St_size = 0;
		Check = true;

		// Chỉ số xe có thể đi, ban đầu có giá trị 1
		int start = 1;

		// Duyệt từng xe 
		for(int i = 0; i < N; i++)
		{
			// Kiểm tra xem nếu đỉnh ngăn xếp có giá trị start thì cho đi
			while(St_size > 0 && Stack[St_size-1] == start)
			{
				St_size--;
				start++;
			}

			// Nếu đầu dãy là start thì cho đi, tăng start lên 1 đơn vị
			if(Order[i] == start) start++;
			else if (St_size > 0 && Stack[St_size-1] < Order[i])
			{
				// Nếu trường hợp này xảy ra thì chắc chắn sẽ không thoả mãn.
				// Vì trường hợp này ta sẽ phải cho điểm ở đầu dãy vào ngăn xếp
				// Mà sau khi cho xong thì tồn tại 1 điểm có giá trị nhỏ hơn 
				// (ưu tiên cao hơn)
				// điểm ở đầu ngăn xếp, mà nó lại không thể đi ra được.
				Check = false;
				break;						
			}
			else // Cho điểm đầu của dãy vào ngăn xếp.
			{
				Stack[St_size] = Order[i];
				St_size++;	
			}
		}

		if(Check) cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}

Code Python:

MAX = 1005
stack = [0] * MAX

while(1):
    n = int(raw_input())
    if n == 0:
        break

    order = map(int, raw_input().split())

    st_size = 0
    check = 1
    start = 1

    for i in range(0, n):
        while (st_size > 0 and stack[st_size - 1] == start):
            st_size -= 1
            start += 1

        if order[i] == start :
            start += 1
        elif st_size > 0 and stack[st_size - 1] < order[i]:
            check = 0
            break
        else:
            stack[st_size] = order[i]
            st_size += 1

    if check == 1:
        print "yes\n"
    else:
        print "no\n"

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!