Ai đó gợi ý cho mình bài này được không? (Có code càng tốt ạ)
Cần gợi ý bài tập giải thuậ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.
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.
Đề bài đưa ra 2 giới hạn là 10^{5} và 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ị l
và r
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} và 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.
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