Cách hoạt động của lệnh lower_bound for pair

[Le_Nhat_Phong]

BÀi toán MSTICK. Có n đoạn gỗ. Để xử lý chúng cần thời gian để chuẩn bị :
(a) Thời gian chuẩn bị cho đoạn gỗ đầu tiên là 1 phút.
(b) Sau khi xử lý xong đoạn gỗ có chiều dài l và trọng lượng w, không mất thời gian xử lý nếu đoạn gỗ tiếp theo có độ dài l’ và trọng lượng w’ thỏa l ≤ l’ and w ≤ w’. Ngược lại mất 1 phút để chuẩn bị.
vd: ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , và ( 4 , 1 ) output ra 2

e có đọc một bài tham khảo giải bài toán trên nhưng không hiểu cách hoạt động của lệnh lower_bound được dùng trong code tham khảo như thế nào, mong mọi người có thể giải thích cho e với ạ, e cám ơn.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int MXV = 10000, N = 5000;
pair<int, int> a[N];
int n, lst[N];
 
void enter() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%d%d", &a[i].first, &a[i].second);
}
 
void solve() {
	sort(a, a+n);
	int maxlen = 1; lst[0] = a[n-1].second;
	for(int i = n-2; i >= 0; --i) {
		int dp = lower_bound(lst, lst+maxlen, a[i].second) - lst;
		if(dp == maxlen) ++maxlen, lst[dp] = a[i].second;
		else lst[dp] = min(lst[dp], a[i].second);
	}
	printf("%d\n", maxlen);
}
 
int main() {
	int tc; scanf("%d", &tc);
	while(tc--) enter(), solve();
	return 0;
}

[Grevyalres_X (Pzanitor)]

https://en.cppreference.com/w/cpp/algorithm/lower_bound

vậy cho 2 pair<int,int> a, b, a <b thì a.first < b.first, nếu a.first < b.first, hoặc nếu a.first = b.first thì a.second < b.second.

lower_bound trong một khoảng trả về con trỏ nhỏ nhất thỏa mãn dấu >= (tùy cách dấu < được định nghĩa).

Bài này ý tưởng là sort các pair theo l, sau đó tìm độ dãy con giảm dài nhất (là số lượng dãy con không giảm dài nhất) trong các w vừa được sắp xếp.

[Le_Nhat_Phong]

E cũng có đọc ý tưởng của bài này nhưng khi áp dụng vào bài code tham khảo trên thì thấy nó không đúng với ý tưởng của bài code trên :)))

[Grevyalres_X (Pzanitor)]

Có gì không đúng thế bạn? Cái code đó giống như thuật tìm dãy con tăng nhưng chạy ngược lại để tìm dãy con giảm thôi.

[Le_Nhat_Phong]

cho e hỏi thêm là cái lst với lst+maxlen đó là cái gì trong lệnh lower_bound vậy ạ

[rogp10]

Có thể hiểu là con trỏ

[Le_Nhat_Phong]

a nói rõ hơn được ko ạ, e vẫn chưa hiểu lắm

[rogp10]

Con trỏ này (vâng, code này đúng là con trỏ) nó chỉ vào một chỗ trong mảng, đi kèm với cấu trúc chứa nó (nhờ vậy mới ++ được).
Để định ra một đoạn mảng cần có “con trỏ” đầu và “con trỏ” đuôi (như std::vector::end()). “Con trỏ” đuôi này không nằm trong đoạn, nó dùng đánh dấu điểm kết thúc (half-open interval) và điều này sẽ tốt hơn vì ghép đoạn liền kề dễ hơn, tính toán cũng dễ hơn.