Hi mọi người. Hiện tại mình đang làm 1 bài tập như sau:
Có thể tóm tắt ngắn gọn là cho một tập segments cho trước (gồm điểm đầu, điểm cuối) rồi một tập hợp điểm (có tọa độ xác định là một số nguyên). Với mỗi điểm trong tập hợp điểm ấy, tìm số lượng segments có chứa điểm ấy.
Thuật toán “ngây thơ” là for với mỗi điểm rồi for các segments xem tọa độ điểm đó có nằm giữa điểm đầu và điểm cuối của segments đang xét không, đpt O(n^2).
Vì kích thước input lên mình implement 1 thuật toán O(nlogn) với ý tưởng như sau:
Mình tạo một vector chứa các pair với first là một số nguyên (có thể là điểm đầu/điểm cuối của 1 segment hoặc 1 điểm trong tập hợp điểm) và second là 1 trong 3 giá trị ký tự ‘l’, ‘r’, ‘p’ (l ký hiệu cái first là 1 điểm đầu của 1 segment, r ký hiệu cái first là 1 điểm cuối của 1 segment, p ký hiệu first là 1 điểm trong tập hợp điểm).
Sau đó mình sort list này tăng dần theo first và có thể dễ dàng đếm được số segments bao quanh 1 điểm bằng điểm đầu và điểm cuối các segments sort theo thứ tự.
VD: Cho 3 điểm x1 = 5, x2 = 8, x3 = 3 và 2 segments [2; 6] và [4; 10]
Khi đó, ta có 1 vector gồm các pair: (2, 'l') ; (3, 'p') ; (4, 'l') ; (5, 'p') ; (6, 'r') ; (8, 'p') ; (10, 'r').
pair đầu tiên là điểm đầu của segment, suy ra pair thứ 2 là điểm có tọa độ 3 sẽ được bao quanh bởi 1 segment.
pair thứ ba là điểm đầu của 1 segment khác, suy ra pair thứ 4 là điểm có tọa độ 5 sẽ được bao quanh bởi 2 segments.
Cứ tương tự như thế …
Mình cài thuật toán như sau:
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
bool compare(const pair<int, char> &p1, const pair<int, char> &p2)
{
return p1.first < p2.first;
}
vector<pair<int, int>> func(const vector<pair<int, char>> &lists)
{
int seg = 0, n = lists.size();
vector<pair<int, int>> res;
for (int i = 0; i < n; ++i) {
if (lists[i].second == 'l') ++seg;
else if (lists[i].second == 'r') --seg;
else res.push_back(make_pair(lists[i].first, seg));
}
return res;
}
int binarySearch(const vector<pair<int, int>> &arr, int left, int right, int key)
{
if (left > right) return -1;
else if (left == right) return arr[left].first == key ? left : -1;
else {
int mid = (left + right) / 2;
if (arr[mid].first == key) return mid;
else if (key < arr[mid].first) return binarySearch(arr, left, mid - 1, key);
else return binarySearch(arr, mid + 1, right, key);
}
}
int main()
{
int s, p, a, b, pos;
cin >> s >> p;
vector<pair<int, char>> lists;
vector<int> points(p);
for (int i = 0; i < s; ++i) {
cin >> a >> b;
lists.push_back(make_pair(a, 'l'));
lists.push_back(make_pair(b, 'r'));
}
for (int i = 0; i < p; ++i) {
cin >> points[i];
lists.push_back(make_pair(points[i], 'p'));
}
sort(lists.begin(), lists.end(), compare);
vector<pair<int, int>> res = func(lists);
for (int i = 0; i < p; ++i) {
pos = binarySearch(res, 0, res.size() - 1, points[i]);
cout << res[pos].second << " ";
}
return 0;
}
Khi chấm trên Coursera bị lỗi Wrong Answer ngay test #4.
Mình suy nghĩ gần tiếng vẫn chưa thấy bug ở chỗ nào, mình up lên đây nhờ mọi người giúp đỡ ạ, ko biết là có sai sót gì trong ý tưởng thuật toán hay code không?
Mình xin cảm ơn trước.
max speed.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?