H
hai6f2009
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Bài 1. Đoạn hoán vị (7 điểm)
Cho dãy số A gồm N số nguyên dương a1, a2,…, aN, mỗi số trong A chỉ xuất hiện đúng 1 ần ( 1≤ N,ai ≤105).
Yêu cầu: Hãy tìm đoạn dài nhất gồm các phần tử trong dãy trên tạo thành một hoán vị các phần tử của tập giá trị {1, 2, …, k} (1 ≤ k ≤ N).
Dữ liệu vào: từ file văn bản PASWAP.INP có cấu trúc như sau:
- Dòng 1: ghi số N.
- Từ dòng 2 trở đi: ghi N số a1, a2,…, aN, giữa các số cách nhau một dấu cách hay dấu xuống hàng.
Kết quả ghi ra file PASWAP.OUT
Nếu không có đoạn nào thỏa mãn thì ghi : 0
Ngược lại:
- Dòng 1 : ghi imax là chỉ số đầu tiên của đoạn dài nhất tìm được trong dãy A.
- Dòng 2 : ghi dmax là số phần tử của đoạn dài nhất.
Ví dụ :
PASWAP.INP
7
10 9 3 4 1 2 8
PASWAP.OUT
3
4
Bài này mình dùng thuật toán gì là hiệu quả nhất vậy các bạn?
Cho dãy số A gồm N số nguyên dương a1, a2,…, aN, mỗi số trong A chỉ xuất hiện đúng 1 ần ( 1≤ N,ai ≤105).
Yêu cầu: Hãy tìm đoạn dài nhất gồm các phần tử trong dãy trên tạo thành một hoán vị các phần tử của tập giá trị {1, 2, …, k} (1 ≤ k ≤ N).
Dữ liệu vào: từ file văn bản PASWAP.INP có cấu trúc như sau:
- Dòng 1: ghi số N.
- Từ dòng 2 trở đi: ghi N số a1, a2,…, aN, giữa các số cách nhau một dấu cách hay dấu xuống hàng.
Kết quả ghi ra file PASWAP.OUT
Nếu không có đoạn nào thỏa mãn thì ghi : 0
Ngược lại:
- Dòng 1 : ghi imax là chỉ số đầu tiên của đoạn dài nhất tìm được trong dãy A.
- Dòng 2 : ghi dmax là số phần tử của đoạn dài nhất.
Ví dụ :
PASWAP.INP
7
10 9 3 4 1 2 8
PASWAP.OUT
3
4
Bài này mình dùng thuật toán gì là hiệu quả nhất vậy các bạn?
