1032 AlvinZH的学霸养成记II

思路

中等题，贪心。

所有课程按照DDL的大小来排序。

维护一个当前时间curTime，初始为0。

遍历课程，curTime加上此课程持续时间d，如果这时curTime大于此课程DDL，表示无法学习此课程，但是我们不减去此课程，而是减去用时最长的那门课程（优先队列队首，课时最长）。

贪心：

假设当前课程为B，被替换课程为A，则有A.d≥B.d，A.e≤B.e。既然curTime+A.d≤A.e，那么curTime+B.d≤B.e绝对成立，保证了B的合法性。

替换之后可学习课程数量没变，但是curTime变小了，有可能可选择更多课程，局部最优策略。

分析

Time complexity : \(O(nlog(n))\).

Space complexity: \(O(n)\).

参考代码

//

// Created by AlvinZH on 2017/11/26.

// Copyright (c) AlvinZH. All rights reserved.

//

#include<cstdio>

#include<algorithm>

#include<iostream>

#include <queue>

using namespace std;

int n;

struct Course {

    int d, e;

}C[100005];

bool cmp(Course p, Course q) {

    return (p.e < q.e);

}

int main()

{

    while(~scanf("%d", &n))

    {

        for(int i = 1; i <= n; i++)

            scanf("%d%d", &C[i].d, &C[i].e);

        sort(C+1, C+n+1, cmp);//按课程的DDL排序

        int curTime = 0;

        priority_queue<int> Q;

        for(int i = 1; i <=n; ++i) {

            curTime += C[i].d;

            Q.push(C[i].d);

            if(curTime > C[i].e) {

                curTime -= Q.top();

                Q.pop();

            }

        }

        printf("%d\n", Q.size());

    }

}

巴特西

2016级算法第六次上机-C.AlvinZH的学霸养成记II

1032 AlvinZH的学霸养成记II

思路

分析

参考代码

最新文章

热门文章