uva1422 训练指南第一章课后习题process求解

[GoogleCodeExporter]

题目复述：
有n个任务，每个任务有3个参数r，d，w。r为任务开始时间，d�
��任务截至时间，工作量为w。任务在给定时间范围内可以被��
�度执行。
这n个任务可以在处理器上进行调度，处理器的工作速度为任�
��整数值。
限制为1<=n<=10000,1<=r<d<=20000,1<=w<=1000.
求出处理器在工作过程中的最大速度的最小值。

所求为最大最小值。
sample input：  
5  
1 4 2  
3 6 3  
4 5 2  
4 7 2  
5 8 1
总得来说，思路应该为二分和贪心，贪心选择最紧迫的任务��
�执行。我的问题是在贪心具体实现上
如样例：将每个时间点加入到一个set中，然后从begin()遍历到e
nd(),如样例所示：set中的时间点为1 3 4 5 6 7 
8，那每次取出一个时间片，然后贪心选择任务。结果是WA。��
�set换成了vector，先排序然后unique。。然后再取时间片，依旧�
��WA。。。。。。。。  
如1 3 4 5 6 7 8，分为1-3 3-4 4-5 5-6 6-7 
7-8这样的时间片，怎么会有错呢。。。
如果不使用时间片，从时间的开始（样例中为1）遍历至时间�
��结束（样例中为8），每循环走一个时间单位。结果为AC。
WA和AC代码对拍了一整夜了，同样也使用了if(w<=0) 
exit(-1)验证服务器数据是否有不合法。服务器数据都是合法的
，但是我的代码依旧为WA。
----------附上2份代码，首先是WA的------------
bool solve(int speed){
   priority_queue<job> q;
   int jobi = 0;
   set<int>::iterator endit = times.end();
   endit--;
   for(set<int>::iterator it = times.begin(); it != endit; it++){
     set<int>::iterator next = it; next++;
     for( ; jobi < n && jobs[jobi].r <= (*it) ; jobi++)
       q.push(jobs[jobi]);

     int work  = speed * ((*next) - (*it));

     while(work>0){
       if(q.empty()) break;
       job jtmp = q.top(); q.pop();
       //cout <<"work: " << work <<"@begin:" << *it << " taskbegin:"<< jtmp.r << " taskend:" << jtmp.d << endl;  
       if(jtmp.w == 0)
     continue;
       if(jtmp.d <= (*it))
     return false;
       if(jtmp.w > work) {
     jtmp.w -= work;
     q.push(jtmp);
     break;
       }else if(jtmp.w == work)
     break;
       else  //jtmp.w < work
     work -= jtmp.w;          
     }
   }
   while(!q.empty())
     if(q.top().w != 0)
       return false;
     else
       q.pop();  
   return true;
}
-----------------------------以下是AC代码-----------
bool solve(int speed){
   priority_queue<job> q;
   int jobi = 0;
   set<int>::iterator endit = times.end();
   endit--;
   int t = *endit,j=*(times.begin());
   while(j<t){
     for( ; jobi < n && jobs[jobi].r <= j ; jobi++)
       q.push(jobs[jobi]);

     int work  = speed ;

     while(work>0){
       if(q.empty()) break;
       job jtmp = q.top(); q.pop();
       //cout <<"work: " << work <<"@begin:" << *it << " taskbegin:"<< jtmp.r << " taskend:" << jtmp.d << endl;  
       if(jtmp.w == 0)
     continue;
       if(jtmp.d <= j)
     return false;      
       if(jtmp.w > work) {
     jtmp.w -= work;
     q.push(jtmp);
     break;
       }else if(jtmp.w == work)
     break;
       else  //jtmp.w < work
     work -= jtmp.w;          
     }
     j++;
   }
   while(!q.empty())
     if(q.top().w != 0)
       return false;
     else
       q.pop();  
   return true;
}
---------------------------------------------------
路过的同学老师工友们，求指教，谢谢。

Original issue reported on code.google.com by zx5z...@gmail.com on 22 Aug 2013 at 9:53

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

问题已解决。
对拍对了两个通宵，都没找出问题。但确实存在问题。

是work会溢出。

Original comment by zx5z...@gmail.com on 23 Aug 2013 at 2:43

[GoogleCodeExporter]

恭喜！

Original comment by rujia....@gmail.com on 3 Sep 2013 at 4:55

• Changed state: Accepted