BYR Achieve · 镜像论坛

题目：有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 我的代码是二分加贪心，贪心选择最紧迫的任务执行。具体实现是首先将所有任务按照开始时间排序，当任务开始时，就将任务加入优先队列，贪心选择截至时间最近最紧迫的任务执行。当任务能全部被执行完，说明这个最大速度是okay的。然后呢，现在我有两份代码：一份是最初写的代码，将每个时间点加入到一个set中，然后从begin()遍历到end(),如样例所示：set中的时间点为1 3 4 5 6 7 8。。。那每次取出一个时间片，然后贪心。结果是WA。。。再参考网上同样使用优先队列的一份题解，从时间的开始（样例中为1）遍历至时间的结束（样例中为8），每循环走一个时间单位。结果为AC。。。我觉的时间片思路应该是没错的，但是，是不是set的使用有什么问题呢，求教？以下为diff： 17d16 < 23,25c22,24 < for(set<int>::iterator it = times.begin(); it != endit; it++){ < set<int>::iterator next = it; next++; < for( ; jobi < n && jobs[jobi].r <= (*it) ; jobi++) --- > int t = *endit,j=*(times.begin()); > while(j<t){ > for( ; jobi < n && jobs[jobi].r <= j ; jobi++) 28c27 < int work = speed * ((*next) - (*it)); --- > int work = speed ; 36,37c35,36 < if(jtmp.d <= (*it)) < return false; --- > if(jtmp.d <= j) > return false; 46a46 > j++; ------------------我是分割线-------------- 完整代码（时间片）： 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; } -------------------我是分割线-------------- 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; } ------------------------泪求debug---------谢谢！！！

已解决，uva1422orla4254泪求debug（仅十多行）