CHỌN VIỆC Có n công việc cần thực hiện trên một máy tính, mỗi việc đòi hỏi đúng 1 giờ chạy máy. Với mỗi việc ta biết thời hạn cuối cùng phải nộp kết quả thực hiện sau khi đã hoàn thành việc đó và tiền thù lao thu được nếu nộp kết quả trước hoặc đúng hạn. Yêu cầu: chỉ có một máy tính, hãy lập lịch để thực hiện đủ n công việc trên máy tính sao cho tổng tiền thu được là lớn nhất với thời gian hoạt động của máy tính là nhỏ nhất. Giả thiết rằng máy tính được khởi động vào đầu ca (thời điểm t = 0) và chỉ tắt máy sau khi đã hoàn thành đủ n công việc. Dữ liệu vào: Đọc từ file BAI3.INP có cấu trúc như sau: Dòng đầu tiên ghi số n (1 n 200) n dòng tiếp theo, dòng thứ i ghi hai số nguyên ti và mi, tương ứng với thời hạn giao nộp kết quả công việc và số tiền thù lao của việc thứ i (1 mi 106 ; 1 ti 104 ). Hai số cùng một dòng cách nhau bởi một dấu cách. Dữ liệu ra: Ghi ra file BAI3.OUT gồm n+1 dòng: - Trong n dòng đầu tiên, dòng thứ j ghi số tự nhiên i cho biết việc thứ i được làm trong đơn vị thời gian j. - Dòng cuối cùng ghi tổng số tiền thu được Ví dụ: BAI3.INP BAI3.OUT 4 4 1 15 2 3 10 3 5 100 1 1 27 137

Vì mình không có đủ thời gian để fix bug lại cho bạn nên bạn thông cảm

Code 1:

#include <iostream>
#include <algorithm>
using namespace std;
struct Job {
    int deadline, profit;
};
bool cmp(Job a, Job b) {
    return a.profit > b.profit;
}
int main() {
    int n;
    cin >> n;
    Job jobs[n];
    for (int i = 0; i < n; i++) {
        cin >> jobs[i].deadline >> jobs[i].profit;
    }
    sort(jobs, jobs+n, cmp);
    bool slot[n] = {false};
    int result[n];
    for (int i = 0; i < n; i++) {
        for (int j = min(n, jobs[i].deadline)-1; j >= 0; j--) {
            if (slot[j] == false) {
                result[j] = i;
                slot[j] = true;
                break;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (slot[i]) {
            cout << result[i]+1 << endl;
            sum += jobs[result[i]].profit;
        }
    }
    cout << sum << endl;
    return 0;
}

//Input:

4
1 15
3 10
5 100
1 27

//Output:

2
4
1
137

Code 2:

#include <iostream>
#include <algorithm>
using namespace std;
struct Job {
    int deadline, profit, id;
};
bool cmp(Job a, Job b) {
    return a.profit > b.profit;
}
int main() {
    int n;
    cin >> n;
    Job jobs[n];
    for (int i = 0; i < n; i++) {
        cin >> jobs[i].deadline >> jobs[i].profit;
        jobs[i].id = i+1;
    }
    sort(jobs, jobs+n, cmp);
    bool slot[n] = {false};
    int result[n];
    for (int i = 0; i < n; i++) {
        for (int j = min(n, jobs[i].deadline)-1; j >= 0; j--) {
            if (slot[j] == false) {
                result[j] = i;
                slot[j] = true;
                break;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (slot[i]) {
            cout << jobs[result[i]].id << endl;
            sum += jobs[result[i]].profit;
        }
    }
    cout << sum << endl;
    return 0;
}

//input

4
1 15
3 10
5 100
1 27

//output

4
2
3
137