Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Nguồn: Đề thi Cử nhân tài năng (Cấu trúc dữ liệu & Giải thuật) – Câu 3.

Cho mảng một chiều ~a~ chứa ~n~ phần tử gồm cả số nguyên dương lẫn nguyên âm. Viết hàm (cùng các hàm phụ trợ, nếu cần thiết) để hoán đổi các con số sao cho dương và âm xen kẽ nhau. Những số dương (hay âm) còn lại (nếu có) sẽ bị đẩy về cuối mảng.

Yêu cầu: Hàm thực thi với chi phí ~\Theta(n)~ và không sử dụng thêm mảng phụ.

Mẫu của hàm như sau:

void Cau3(int a[], int n);

Để nộp bài trên web, chương trình đọc dữ liệu, gọi Cau3(a, n) rồi in mảng kết quả. Theo ví dụ của đề, mảng kết quả luôn bắt đầu bằng số dương: dương, âm, dương, âm, …

Dữ liệu vào

• Dòng đầu tiên là số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (mỗi số khác ~0~).

Kết quả

• In ra ~n~ số nguyên trên một dòng: mảng sau khi hoán đổi, các số cách nhau bởi dấu cách.
• Gọi ~m = \min(~số dương, số âm~)~. Mảng in ra phải gồm đúng các số của mảng ban đầu (chỉ đổi thứ tự), ~2m~ vị trí đầu xen kẽ dương – âm bắt đầu bằng số dương, các số còn lại phía sau cùng một dấu.
• Có thể có nhiều đáp án đúng, in ra một đáp án bất kỳ.

Giới hạn

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le |a_i| \le 10^9~
• Mảng có thể toàn số dương hoặc toàn số âm.

Sample Input 1

10
8 -8 -7 -9 3 3 2 -2 -7 10

Sample Output 1

3 -8 2 -9 3 -7 8 -2 10 -7

Sample Input 2

10
-7 -9 -6 10 5 -7 -5 -10 8 4

Sample Output 2

5 -9 10 -10 8 -7 4 -6 -5 -7

Sample Input 3

10
-3 -1 4 8 -8 1 1 5 10 8

Sample Output 3

8 -1 4 -3 1 -8 1 5 10 8

Giải thích

Ở ví dụ 3, mảng có 7 số dương và 3 số âm: xen kẽ được 3 cặp 8 -1 4 -3 1 -8, còn dư 4 số dương 1 5 10 8 nằm ở cuối. Thứ tự các số không quan trọng, mọi cách xếp thỏa mãn điều kiện đều được chấp nhận.