算法题：家庭作业

问题描述

老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10，要求在6天内交，那么要想拿到这10学分，就必须在第6天结束前交。 每个作业的完成时间都是只有一天。例如，假设有7次作业的学分和完成时间如下： 作业号 1 2 3 4 5 6 7 期 限 1 1 3 3 2 2 6 学 分 6 7 2 1 4 5 1

你的任务就是找到一个完成作业的顺序获得最大学分。

输入格式

第一行一个整数N，表示作业的数量； 接下来N行，每行包括两个整数，第一个整数表示作业的完成期限，第二个数表示该作业的学分。

输出格式

输出一个整数表示可以获得的最大学分。保证答案不超过C/C++的int范围。

样例

输入

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

输出

15

数据范围

• 对于20%的数据，N≤10^3；
• 对于40%的数据，N≤10^4；
• 对于60%的数据，N≤10^5；
• 对于100%的数据，N≤10^6，作业的完成期限均小于7×10^5

解决方案

思路

先优先取得分高的，如果然后记录时段，如果时段已经被记录过了，就往前找空闲时段（使用类似并查集的思想加速查找前面的空闲时段）。

代码

#include <iostream>
#include <algorithm>

using namespace std;

struct Work {
    int time;
    int mark;
};

bool comp(Work a, Work b) {
    return a.mark > b.mark;
}

const int N = 7e6 + 5;

int days[N];
Work arr[N];

int pre[N];

void init(int n) {
    for (int i = 1; i < n; ++i) {
        pre[i] = i - 1;
    }
}

// 往上找为空的
int find(int x) {
    if (days[x] == 0)
        return x;

    pre[x] = find(pre[x]);
    return pre[x];
}


int main() {

    int n;

    cin >> n;
    init(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &arr[i].time, &arr[i].mark);
    }

    sort(arr, arr + n, comp);

    int ans = 0;
    for (const auto &item: arr) {
        int time = item.time;
        int mark = item.mark;

        int t = find(time);
        if (t > 0) {
            days[t] = mark;
            ans += mark;
            if (t != time)
                pre[time] = pre[t];
        }
    }

    cout << ans;

    return 0;
}