Bài toán
Tìm dãy con tăng thực sự của một dãy số.
Độ phức tạp
O(n logn)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
int nxt[1230997];
int dump[1230997];
int rslt[1230997];
int lis(int a[], int n) {
int r = 0, i, j;
for (i = 1; i <= n; i++)
if (r == 0 || a[i] > a[dump[r]]) {
nxt[i] = (r == 0 ? 0 : dump[r]);
dump[++r] = i;
} else {
int ll = 1, rr = r, j = (ll + rr) / 2;
while (ll != j && j != rr) {
if (a[i] <= a[dump[j]])
rr = j;
else
ll = j;
j = (ll + rr) / 2;
}
for (j = ll; j <= rr; j++) {
if (a[i] <= a[dump[j]]) {
nxt[i] = dump[j - 1];
dump[j] = i;
break;
}
}
}
j = r;
for (i = dump[r]; i != 0; i = nxt[i]) rslt[j--] = i;
return r;
}
int n;
int a[1230997];
int main() {
int i;
scanf("%d", &n);
for (i = 1; i <= n; i++) scanf("%d", &a[i]);
int r = lis(a, n);
printf("%d\n", r);
printf("\n");
for (i = 1; i <= r; i++)
printf("%d\n", a[rslt[i]]);
}
Nhận xét
Code này đã được dùng để nộp cho một bài tập trên UVa.
Phần nhập xuất dữ liệu đã được thay đổi để bám sát với chủ đề.
Với mỗi a[i], tìm dump[j] sao cho a[i]<=a[dump[j]]. Nếu tất cả dump[j] với 1<=j<=r không thỏa mãn (hay đơn giản là a[i]>a[dump[r]]) thì dump[++r]=i và cập nhật next[i]. Nếu tìm được dump[j] thì cập nhật next[i] và dump[j] như code.
Mô tả
next[]
Nếu chọn phần tử thứ i thì hãy chọn phần tử next[i]. Nếu chọn i mà next[i]=0 thì không cần chọn thêm số nào nữa.
next[] là mảng chứa các chỉ số, không phải là giá trị.
dump[]
a[dump[1]] .. a[dump[r]] là một dãy tăng, tuy nhiên đây không phải là kết quả bài toán, mảng này chỉ là phụ.
dump[] là mảng chứa chỉ số, không phải giá trị.
rslt[]
mảng này chứa các chỉ số của các phần tử có trong dãy kết quả. Kết quả cần in ra là a[rslt[1]]..a[rslt[r]].
rslt[] là mảng chứa chỉ số, không phải giá trị.
r
Độ dài của dãy tăng ở thời điểm hiện tại. 0<=r<=n.
Các lỗi thường gặp
Runtime error
- Chú ý rằng các mảng next, dump, rslt là mảng lưu chỉ số, không phải lưu giá trị.
Wrong answer
- Chú ý rằng điều kiện tăng r là r==0 || a[i]>a[dump[r]] chứ không chỉ là a[i]>a[dump[r]]
- Chú ý rằng điều kiện của dump[j] được chọn với mỗi a[i] là a[i] <= a[dump[j]]
- Chú ý rằng lệnh cập nhật next[i] là next[i]=dump[j-1], chứ không phải là next[i]=next[dump[i]].
Time limit exceeded
- Kiểm tra lại phần chặt nhị phân, xem bài hướng dẫn về chặt nhị phân tại Chặt nhị phân.