Hướng dẫn cho LQDOJ Cup 2023 - Round 3 - Schedule
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors: ,
Subtask \(1\)
Tutorial
Bởi vì thời gian hoàn thành một công việc bất kỳ được giới hạn chỉ trong một ngày, vậy nên kết quả bài toán là giá trị lớn nhất của số lượng lõi tối thiểu cần để hoàn thành các công việc có cùng ngày thực hiện và hoàn thành.
Độ phức tạp: \(O(m\log(m))\)
Solution
#include <bits/stdc++.h>
using namespace std;
struct Task {
long long nPart;
int bg, ed;
};
const int N = 1e5+7;
int numDay, numTask;
Task tasks[N];
long long solve() {
long long res = 0;
long long sum = 0;
for (int i = 1; i <= numTask; ++i) {
sum += tasks[i].nPart;
if (i == numTask || tasks[i].bg != tasks[i+1].bg) {
res = max(res, sum);
sum = 0;
}
}
return res;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
freopen("schedule.inp", "r", stdin);
freopen("schedule.out", "w", stdout);
cin >> numTask >> numDay;
for (int i = 1; i <= numTask; ++i) {
cin >> tasks[i].nPart >> tasks[i].bg >> tasks[i].ed;
}
sort(tasks+1,tasks+numTask+1, [&](const Task& a, const Task& b) {
return a.bg < b.bg || (a.bg == b.bg && a.ed < b.ed);
});
cout << solve();
return 0;
}
Subtask \(2\)
Tutorial
Dùng kĩ thuật chặt nhị phân để tìm kiếm số lượng lõi tối thiểu:
Để kiểm tra liệu có thể sử dụng \(x\) lõi để hoàn thành hết công việc trong thời gian yêu cầu hay không, ta có thể làm như sau:
- Xem một công việc gồm \(k\) phần như là \(k\) công việc khác nhau, khi đó số lượng công việc là tổng số lượng phần của \(m\) công việc.
- Sắp xếp các công việc đó theo thứ tự thời gian bắt đầu không giảm.
- Duyệt các ngày từ \(1\) đến \(n\), khi xét đến ngày thứ \(i\), thêm các công việc có thời điểm bắt đầu là \(i\) vào tập hợp, như thế thì vào ngày đó ta sẽ ưu tiên hoàn thành tối đa \(x\) công việc có thời điểm kết thúc sớm hơn và bỏ chúng ra khỏi tập hợp.
- Nếu như khi xét đến ngày \(i\) mà trong tập hợp có chứa một công việc có thời điểm kết thúc nhỏ hơn \(i\), thì khi đó ta suy ra được là không thể sử dụng \(x\) lõi để hoàn thành hết công việc trong thời gian yêu cầu được.
- Nếu như đã xét hết đến ngày thứ \(n\) mà vẫn còn công việc trong tập hợp thì không thể sử dụng \(x\) lõi, và có thể nếu ngược lại.
\(O(n \log(sum(k_i)))\)
Solution
#include <bits/stdc++.h>
using namespace std;
struct Task {
long long nPart;
int bg, ed;
};
const int N = 1e5+7;
int numDay, numTask;
Task tasks[N], temp_tasks[N];
struct cmp {
bool operator () (const Task* a, const Task* b) {
return a->ed > b->ed;
}
};
bool isOk(long long numWorker) {
for (int i = 1; i <= numTask; ++i) {
temp_tasks[i].nPart = tasks[i].nPart;
}
priority_queue<Task*, vector<Task*>, cmp> heap;
int taskId = 1;
for (int curDay = 1; curDay <= numDay+1; ++curDay) {
while (taskId <= numTask && temp_tasks[taskId].bg == curDay) {
heap.push(temp_tasks+taskId);
taskId++;
}
if (!heap.empty() && heap.top()->ed < curDay) {
return false;
}
int cnt = 0;
while (!heap.empty() && cnt < numWorker) {
Task* task = heap.top();
if (cnt + task->nPart >= numWorker) {
task->nPart -= numWorker - cnt;
cnt = numWorker;
} else {
cnt += task->nPart;
task->nPart = 0;
}
if (task->nPart == 0) {
heap.pop();
}
}
}
return true;
}
long long solve() {
long long l = 1;
long long r = 1e18;
while (l < r) {
long long m = l+r>>1;
if (isOk(m)) {
r = m;
} else {
l = m+1;
}
}
return l;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
freopen("schedule.inp", "r", stdin);
freopen("schedule.out", "w", stdout);
cin >> numTask >> numDay;
for (int i = 1; i <= numTask; ++i) {
cin >> tasks[i].nPart >> tasks[i].bg >> tasks[i].ed;
}
sort(tasks+1,tasks+numTask+1, [&](const Task& a, const Task& b) {
return a.bg < b.bg || (a.bg == b.bg && a.ed < b.ed);
});
for (int i = 1; i <= numTask; ++i) {
temp_tasks[i] = tasks[i];
}
cout << solve();
return 0;
}
Subtask \(3\)
Tutorial
Ở Subtask này, mỗi công việc chỉ có đúng một phần, vẫn nên có thể áp dụng thuật toán ở Subtask 2, nhưng bây giờ không còn giới hạn giá trị \(n\) nữa, vậy nên ta phải duyệt các thời điểm phân biệt trong các thời điểm giới hạn của các công việc.
Độ phức tạp: \(O(m \log(m)^2)\)
Subtask \(4\)
Tutorial
Dùng kĩ thuật chặt nhị phân kết quả để tìm số lượng tối thiểu:
Ta có thể làm như sau :
- Sắp xếp các công việc theo thứ tự thời gian bắt đầu không giảm.
- Ta sẽ có biến \(day\) tượng trưng cho ngày hiện tại. Khởi tạo là 0.
- Dùng hàng đợi ưu tiên và tham lam như sau :
Duyệt qua từng công việc : Mỗi công việc ta thêm \(t_i\) vào hàng đợi
Giả sử công việc \(i\) có ngày bắt đầu là \(s_i\) thì ta cần xử lý các công việc trong hàng đợi
có ngày hết hạn trước \(s_i\) . Tức là công việc trong hàng đợi có \(t\) là ngày hết hạn và \(t\) \(<\) \(s_i\) thì ta
cần dịch số ngày \(day\) lên \(t\) , nếu day >= \(t\) thì \(t\) đã không thể hoàn thành nên số lõi hiện tại
là không hợp lệ. Ngược lại ta cập nhật lại hàng đợi theo số phần công việc sẽ được hoàn thành từ ngày \(day\) -> \(t\).
Sau đó ta gán \(day = t\).
Ngoài ra , sau khi xử lý các công việc có ngày hết hạn trước \(s_i\) , thì \(day\) có thể < \(s_i -1\) nên ta cần \(day\) = \(s_i - 1\).
Cập nhật lại các công việc còn lại trong hàng đợi với số lượng phần công việc có thể hoàn thành từ \(day\) -> \(s_i - 1\).
Sau đó mới đẩy ngày kết thúc của công việc thứ \(i\) vào hàng đợi.
Độ phức tạp: \(O(m \log(m)^2)\)
Solution
int s = 0; // biến day
long long t = 0;
for(int i = 1; i <= n ;i++)
{
//Xử lý các công việc có ngày hết hạn < ngày bắt đầu của công việc hiện tại
while(!pq.empty() && pq.top().first < job[i].s)
{
long long temp = pq.top().first - s;
s = pq.top().first; // cập nhật ngày hiện tại lên ngày pq.top().first
if(temp <= 0)return false; // Không thể hoàn thành công việc
if(Check_MUL(value , temp)) // long long overflow
{
t = LIMIT; // LIMIT = 1 x 10^18
}else
{
t = value * temp;
}
//Cập nhật hàng đợi
while(!pq.empty() && t > 0)
{
pair<long long , long long >lmao = pq.top();
pq.pop();
long long sub = min(t , lmao.second);
lmao.second -= sub;
t -= sub;
if(lmao.second != 0)pq.push(lmao);
}
}
//Kiểm tra tồn tại công việc hết hạn trước ngày hiện tại
if(!pq.empty() && pq.top().first <= s)
{
return false;
}
//Đẩy biến day lên (ngày bắt đầu của công việc thứ i) -1
long long temp = job[i].s - s - 1 ;
s = job[i].s-1;
if(temp == 0)
{
pq.push(make_pair(job[i].t , job[i].values));
continue;
}
if(Check_MUL(value , temp)) // long long overflow
{
t = LIMIT; // LIMIT = 1 x 10 ^ 18
}else
{
t = value * temp;
}
//Cập nhật hàng đợi
while(!pq.empty() && t > 0 )
{
pair<long long , long long >lmao = pq.top();
pq.pop();
long long sub = min(t , lmao.second);
lmao.second -= sub;
t -= sub;
if(lmao.second != 0)pq.push(lmao);
}
//Đẩy công việc mới vào
pq.push(make_pair(job[i].t , job[i].values));
}
while(!pq.empty())
{
long long temp = pq.top().first - s;
s = pq.top().first;
if(temp <= 0)return false;
if(Check_MUL(value , temp))
{
t = LIMIT;
}else
{ // long long overflow
t = value * temp;
}
while(!pq.empty() && t > 0)
{
pair<long long , long long >lmao = pq.top();
pq.pop();
long long sub = min(t , lmao.second);
lmao.second -= sub;
t -= sub;
if(lmao.second != 0)pq.push(lmao);
}
}
return true;
Bình luận