UVa 1422：Processor 任务处理问题

题目大意：有n个任务送到处理器处理，每个任务信息包括r，d，w，r代表开始时间，w代表必须要结束的时间，w指需要多少时间处理。

其中处理器的处理速度可以变速，问处理器最小需要多大速度才能完成工作？

输入：

3
5
1 4 2
3 6 3
4 5 2
4 7 2
5 8 1
6
1 7 25
4 8 10
7 10 5
8 11 5
10 13 10
11 13 5
8
15 18 10
20 24 16
8 15 33
11 14 14
1 6 16
16 19 12
3 5 12
22 25 10

输出：

2
5
7

题目显示是Moderate（中等难度），但是实际上是好困难的题目,没有这种处理思想是做不出来的。

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

处理思想：每秒的速度相当于一个柱子，每个柱子能容纳多少w，优先处理紧急的任务！

灵活运用二分法，优先队列贪心法最后才能解出来.

原题目如下：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4168

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
using namespace std;  

struct Work
{
    int r, d, w;
    bool operator<(const Work &w2) const//原来priority_queue的<也不容易写对，注意const
    {
        return d > w2.d;
    }
};  

inline bool compare_r(const Work &a, const Work &b)
{
    return a.r < b.r;
}  

class Process
{
public:
    const static int MAX_SPEED = 5000; //最大肯定不过：20000 * 1000;
    enum SPEED
    {
        OVER_SPEED,
        NEED_SPEED
    };  

    void processing()
    {
        int T = 0;
        cin>>T;  

        int n = 0;
        Work tmp;
        while (T--)
        {
            cin>>n;
            vector<Work> ws;
            for (int i = 0; i < n; i++)
            {
                cin>>tmp.r>>tmp.d>>tmp.w;
                ws.push_back(tmp);
            }
            sort(ws.begin(), ws.end(), compare_r);
            cout<<biSearchSpeed(ws, 1, MAX_SPEED)<<endl;
        }
    }  

    int biSearchSpeed(vector<Work> &ws, int low, int up)
    {
        while (low <= up)
        {
            int mid = low + ((up-low)>>1);
            if (OVER_SPEED == adjustSpeed(mid, ws)) up = mid-1;
            else low = mid+1;
        }
        return low;
    }  

    //有点Leetcode题目的蓄水问题思想。
    //处理思想：每秒的速度相当于一个柱子，每个柱子能容纳多少w，优先处理紧急的任务！
    SPEED adjustSpeed(const unsigned speed, vector<Work> &ws)
    {
        priority_queue<Work> pq;
        int curSec = 1;
        int i = 0;
        while (i < ws.size() || !pq.empty() )
        {
            for ( ; i < ws.size() && ws[i].r <= curSec; i++) pq.push(ws[i]);
            int secPower = speed;
            while (secPower && !pq.empty())
            {
                //注意头疼的错误：这里是要操作top，不能是副本！！！
                Work wk = pq.top();
                if (wk.d <= curSec) return NEED_SPEED;//错误：注意一定要是<=，否则答案错误！！！
                pq.pop();
                if (wk.w > secPower)
                {
                    wk.w -= secPower;//use up the power in this sec
                    pq.push(wk);
                    secPower = 0;// has been used up
                }
                else secPower -= wk.w;
            }
            curSec++;
        }
        return OVER_SPEED;
    }
};

调试函数：

int main()
{
    Process pro;
    pro.processing();
    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索处理器
， include
， 贪心法 最小圈基问题
， 题目
， 速度
， 处理
任务
木块问题 uva101、多任务处理、多任务处理能力、批处理导入计划任务、批处理添加计划任务，以便于您获取更多的相关知识。