Cần gợi ý bài tập giải thuật

Ai đó gợi ý cho mình bài này được không? (Có code càng tốt ạ)

Với lại bạn nên copy text để người muốn giúp dễ copy và SEO được nếu người đến sau có cùng câu hỏi thì dễ search google.

2 Likes

Mình đã thử code thế này rồi nhưng lại bị sai, bạn xem giúp mình được không vậy?

#include <bits/stdc++.h>
using namespace std;
const long long p=1e8;
long long n,m,toa1[p+5],toa2[p+5];
int main() {
    long long d=0;
    cin >> n >> m;
    for (long long i=0; i<n; i++) cin >> toa1 >> toa2;
        for (long long i=0; i<n; i++) {
        for (long long j=i+1; j<n; j++) {
            for (long long k=toa1[i]; k<=toa2[i]; k++) {
                for (long long h=toa1[j]; h<=toa2[j]; h++) {
                    if (k!=h) {
                        cout << "YES\n" << i+1 << j+1;
                        d=1;
                        break;
                    }
                }
                
            }
        }
    }
    if (d==0) cout << "NO";
}

Sorry bạn, bạn viết 5 vòng for lồng nhau debug hoa cả mắt @@, giải thuật không phải thế mạnh của mình. Chờ người bên dưới vậy.

2 Likes

Đề bài đưa ra 2 giới hạn là 10^{5}10^{9}, nhưng cái bạn khai báo chả liên quan gì sất.

Việc so sánh 2 đoạn [l, r] có giao nhau hay không chỉ là so sánh các giá trị lr của chúng. Trong trường hợp này thì cùng lớn hơn hoặc cùng bé hơn sẽ không giao nhau.
(l1 < l2 && r1 < l2) || (l2 < l1 && r2 < l1)

Bạn dùng thuật toán gì mà dùng đến 4 vòng lặp lồng nhau cho giá trị có thể lên đến 10^{5}10^{9} như vậy? Tính sơ sơ là nó đã có thể lặp lên đến 10^{20} thời gian thực thi chắc tính bằng giờ chứ không phải là giây.

3 Likes

Bài này mình nghĩ cũng đơn giản thôi.
Bạn sắp xếp các tour theo l rồi đến r tăng dần
Ví dụ:
2 4
1 3
1 2
3 5
Thành
1 2
1 3
2 3
3 5

Duyệt các tour i từ 1 -> n. Với mỗi tour i, tìm tour j với j > i sao cho ri < lj (cái này mình dùng tìm kiếm nhị phân). Vậy đpt là nlogn

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