Wooden Sticks

Xem dạng PDF
Gửi bài giải
Điểm: 0,22 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Nguồn bài:
Taejon 2002
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ đoạn gỗ. Để xử lý chúng cần thời gian để chuẩn bị :

  • Thời gian chuẩn bị cho đoạn gỗ đầu tiên là ~1~ phút.
  • 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 \leq l'~ and ~w \leq w'~. Ngược lại mất ~1~ phút để chuẩn bị.

Tìm thời gian chuẩn bị ít nhất cho ~N~ đoạn gỗ.

Ví dụ có ~5~ đoạn ~( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 )~ và ~( 4 , 1 )~, thì thời gian ít nhất là ~2~ vì có thể xử lý theo thứ tự như sau ~( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .~ ​

Input

Dòng đầu là số lượng test, ~T \leq 100~. Mỗi test gồm:

  • Dòng đầu là số nguyên dương ~N \leq 5000~.
  • Sau đó là ~N~ dòng gồm ~N~ cặp số nguyên dương ~(l_1,w_1),(l_2,w_2),\ldots,(l_N,w_N)~, ~l_i,w_i \leq 10000~, là độ dài và trọng lượng của các khối gỗ.

Output

In ra ~T~ dòng, mỗi dòng là thời gian ít nhất để chuẩn bị các đoạn gỗ của test đó.

Sample Input

3

5 
4 9 
5 2 
2 1 
3 5 
1 4

3 
2 2 
1 1 
2 2

3 
1 3 
2 2 
3 1

Sample Output

2
1
3

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    TysonWestley  đã bình luận lúc 7, Tháng 12, 2025, 3:17

    Đây là logic của bài toán: +) ta nhận thấy rằng, ta luôn phải so sánh 2 giá trị với nhau nếu L<=L" và R<=R" thì không mất thời gian và ngược lai. để giải quyết vấn đề này :ta đi sort thằng L trước. và bài toán ta chỉ so sánh R.

    +)Sau khi sort theo L tăng dần, bài toán chỉ còn lại việc so sánh theo R.

    Để xử lý R tối ưu, ta dùng binary search:
    đưa các giá trị R vào một mảng, và với mỗi R mới:
    nếu R ≥ phần tử tại vị trí tìm được → cập nhật phần tử đó bằng R;
    ngược lại → thêm một nhóm mới.
    Kết quả chính là độ dài mảng này, tức số đoạn không thể gộp được với nhau.

    code:

    include <bits/stdc++.h>

    using namespace std;

    define ll long long

    void solve() { ll n ;cin >> n; vector< pair< ll, ll>> a(n+1); for(int i=1; i<=n;i ++) { cin >> a[i].first >> a[i].second;

    }

    sort(a.begin() + 1, a.begin() + n + 1); vector < ll > ans; for(int i =1; i<=n; i++) { auto idx = lowerbound(ans.begin(), ans.end(),-a[i].second); if ( idx == ans.end()) { ans.pushback(-a[i].second); } else{ *idx = -a[i].second; } } cout << ans.size() << endl; } int main() { int t; cin >> t; while (t--) { solve(); }

    } thanks mọi người


  • 1
    vominhmanh10  đã bình luận lúc 12, Tháng 10, 2025, 7:45 ← sửa 7

    sắp sếp các li tăng dần, bằng thì wi tăng dần, ta cần chia nhóm tăng dần tối thiểu để tiết kiệm thời gian và đáp án nằm ở số nhóm, số nhóm dãy con tăng tối thiểu để phân chia một dãy bằng độ dài dãy giảm dài nhất với wi, LDS tối ưu với tìm kiếm nhị phân

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll t, n;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        vector< pair< ll, ll>> a(n);
        for (auto &x : a) cin >> x.first >> x.second;
        sort(a.begin(), a.end());
        vector<ll> lis;
        for (int i = 0; i < n; i++) {
            auto idx = lower_bound(lis.begin(), lis.end(), -a[i].second);
            if (idx == lis.end()) lis.push_back(-a[i].second);
            else *idx = -a[i].second; 
        }
        cout << lis.size() << "\n";
    }
}

  • -5
    chaudiensdk5  đã bình luận lúc 4, Tháng 12, 2024, 8:03 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -2
      vuongbankien012  đã bình luận lúc 17, Tháng 9, 2025, 13:09

      mình làm bằng chặt nhị phân trên segment tree, mà khá chậm không biết mn làm như nào=))