UVa 1422：Processor 任务处理问题

UVa 1422：Processor 任务处理问题2015-02-25题目大意：有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（中等难度），但是实际上是好困难的题目,没有这种处理思想是做不出来的。

处理思想：每秒的速度相当于一个柱子，每个柱子能容纳多少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 secpq.push（wk）;secPower = 0;// has been used up}else secPower -= wk.w;}curSec++;}return OVER_SPEED;}};

调试函数：

int main（）{Process pro;pro.processing（）;return 0;}

From：csdn博客靖心