Hỏi về dãy con tăng dài nhất

#1

Cho mình hỏi cách hoạt động của it trong vòng for với ạ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> v;
for (int i = 0; i < n; i++) {
    auto it = lower_bound(v.begin(), v.end(), a[i]);
    if (it != v.end())  *it = a[i];
     else
     v.push_back(a[i]);
}

	cout<<v.size();
}
#2

bạn có thể mô tả bạn đang làm gì và copy code lên thay vì hình ảnh được không? Mình thấy bạn có 1 mảng, và vòng for của bạn để thực thi hàm lower_bound cho từng phần tử trong mảng, biến it để lưu giá trị trả về sau khi chạy hàm.

1 Like
#3

biến it nó lưu trữ sau mỗi vòng lặp à bạn

#4

bạn thử debug ở đây thì sẽ thấy giá trị i và it thay đổi như thế nào sau mỗi vòng lặp, mình thấy it ở đây không có mục đích lưu trữ mà chỉ làm điều kiện để cho hàm push_back chèn giá trị vào vector thôi.

#5

họ gán *it = a[i] làm gì vậy bạn nhỉ

#6

dòng đấy bạn mới thêm hả, vừa nãy mình không thấy, theo mình gán *it = a[i]; ở đây không có tác dụng gì vì vòng for tiếp theo it cũng được gán lại thôi.

#7

Để tối ưu dãy đó.

Vì ô thứ k phải là số bé nhất lập thành dãy tăng có độ dài k+1.

2 Likes
#8

ở cái dùng if kia mình thay *it=a[i] bằng continue nhưng kết quả sai, còn giữ *it=a[i] thì kq đúng

#9

là sao ạ em vẫn chưa hiểu

#10

Ở đây it nôm na là một con trỏ vào bên trong vector v đấy.

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