Tìm lỗi dãy con tăng dài nhất

Mình có đoạn code này

#include <bits/stdc++.h>

using namespace std;
int n, a[50000], h[50000], res;

int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;i++) scanf("%d", &a[i]);
    h[1] = 1; res = 1;
    for(int i = 2;i <= n; i++){
        if(a[i] < a[h[1]]){
            h[1] = i;
        }
        else
        if(a[i] > a[h[res]]){
            res++;
            h[res] = i;
        }
        else{
            int l = 1 , r = res;
            int pos;
            while(l <= r){
                int mid = l + r >> 1;
                if(a[i] > a[h[mid]])
                	//pos = mid,
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            pos = l - 1; // ???

                h[pos+1] = i;
        }
    }
    printf("%d", res);
    return 0;
}

edit: đề bài nhập một số n; dòng sau nhập dãy n số. tìm dãy con tăng dài nhất

Cách mình code chỗ đóng cmt kia có giống nhau không. tại sao submit 2 code thì cách viết trong cmt bị sai. cảm ơn mọi người

mình không hiểu nó là gì :sweat::sweat::sweat::sweat:

2 Likes

Bạn nên đưa đề bài lên hoặc chí ít là viết ra là code của bạn đang làm cái gì chứ đọc 1 đống biến a,b,c x,y,z thì m cũng đến lộn ruột luôn @@

1 Like

Viết lại để bạn tham khảo cách đặt biến, indentation, và spacing giữa các lệnh cho phù hợp.

int left = 1;
int right = res;
int position;

while (left <= right) {
  int middle = (left + right) / 2;
  if (arr[i] > arr[arr_index[middle]) {
    // position = middle; (1)
    left = middle + 1;
  } else {
    right = middle - 1;
  }
}

position = left - 1; // (2)
arr_index[position + 1] = i;

Theo mình đoán, đoạn code trên thực hiện binary search, output của nó được gán lại biến position.
Precondition trước khi thực hiện while là:left <= right.


Giả sử left = right = p với p là giá trị nguyên. Mà middle = (p + p) / 2 = p.
Do đó left = right = middle = p.
Ngoài ra, lệnh if luôn làm cho left > right. Lần lặp tiếp theo không bao giờ thực hiện.

Trường hợp 1:
Nếu (1) thực hiện, (2) không thực hiện. position nhận giá trị là middle, hay position = p

Trường hợp 2:
Nếu (2) thực hiện, (1) không thực hiện. position nhận giá trị left - 1, có 2 trường hợp:

  • 2.1: left bị thay đổi bởi if:
    • left = middle + 1 = p + 1
    • position = left - 1 = (p+1) - 1 = p.
  • 2.2: left không bị thay đổi bởi if:
    • position = left - 1 = middle - 1 = middle = p-1

TH 1 chỉ gán 1 giá trị p, TH 2 gán tuỳ điều kiện của if mà gán p hay p-1.
Do đó, 2 đoạn code cho kết quả khác nhau.


Mình không biết bài của bạn là gì, mình chỉ dựa code của bạn mà đoán.

3 Likes

nhưng cái if kia mình chắc chắn luôn xảy ra. nên cái left với cái position trong đấy luôn cùng thay đổi

Chắc chắn xảy ra thì bạn nên đưa loop invariant của bạn, không thể đoán mò được.

Search về loop invariant để biết thêm về chứng minh correctness của 1 program.

3 Likes

pos của bạn là cái gì?

Nếu bài này là tìm dãy con tăng liên tiếp, thì thuật toán của bạn quá rườm rà.

Nếu bài này là tìm dãy con tăng không liên tiếp, thì thuật toán của bạn sai.

1 Like

Tăng không liên tục nghĩa là sao ạ.
Bài kia mình làm là tìm độ dài dãy con tăng liên tiếp dài nhất. Bạn chỉ mình cách nhanh hơn được không. Trong code của mình h[i] là dãy chỉ số của dãy con tăng mà mình liên tục cập nhật. pos là vị trí đầu tiên để chèn i vào sau nó giữa dãy h[] thỏa mãn dãy h[i] luôn là dãy chỉ số mà a[h[i]] luôn tăng

Đã là dãy liên tục thì không có chèn gì được :smiley: đọc 1 mạch từ đầu đến cuối.

1 Like

chắc bác chưa hiểu ý tưởng của mình rồi

^ Vì bạn hỏi câu này :smiley:


Ý tưởng thì ngon, nhưng mà thuật toán tìm nhị phân thì khá căng. Bài toán sẽ bao gồm phần tìm số bé nhất trong mảng tăng mà >= số đã cho. Tức là đầu bên phải khi chia nhị phân.
Để viết đúng tìm nhị phân thì chia mảng cho đúng là quan trọng nhất: < và >=

2 Likes

Chắc bạn đọc ở một số trang dùng chặt nhị phân. Nhưng cách đó là dành cho bài toán tìm dãy con tăng không liên tiếp dài nhất.

Bài này rất đơn giản. Xét 1 chỉ số i != 0 (phần tử a[i] không phải ở đầu). Chỉ có 2 trường hợp xảy ra:

  • a[i-1] < a[i] -> a[i] nối thêm vào dãy tăng liên tiếp.

  • a[i-1] >= a[i] -> a[i] là điểm bắt đầu của 1 dãy tăng liên tiếp khác.

Mỗi lần gặp một a[i] nào đó là điểm bắt đầu của 1 dãy tăng liên tiếp mới thì cập nhật lại độ dài. Chi tiết thế nào thì bạn suy nghĩ thêm một chút.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?