首页 > 代码库 > LA 4254 处理器（二分+贪心）
LA 4254 处理器（二分+贪心）
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2255
题意：
有n个任务，每个任务有3个参数ri，di和wi，表示必须在时刻[ri,di]之内执行，工作量为wi。处理器的速度可以为任意值，任务不一定要连续执行，可以分成若干块，求最大速度的最小值。
思路：
最大值的最小值问题可以考虑用二分法来做。
这道题目怎么判断速度合法是关键，我们可以使用秒为单位来判断。计算时使用贪心法，d值小的优先处理。用一个优先队列（d值小的优先级高），时间以秒为单位从1开始一次增加，如果一个任务的r值等于了当前时间t，说明该任务可以开始执行了，那么就把它加入到队列中。每个一秒的时间内处理该段时间内可以执行的d值最小的任务。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<queue> 5 using namespace std; 6 7 const int maxn = 10000 + 5; 8 9 int n;10 11 struct node12 {13 int r, d, w;14 bool operator <(const node& rhs) const15 {16 return d>rhs.d; //右坐标越大的优先级越低17 }18 }a[maxn];19 20 bool cmp(node a, node b)21 {22 return a.r < b.r;23 }24 25 bool check(int speed)26 {27 priority_queue<node> q;28 int t = 1, cnt = 0;29 while (cnt<n || !q.empty())30 {31 while (cnt < n && a[cnt].r == t) q.push(a[cnt++]);32 int s = speed;33 while (!q.empty() && s!=0)34 {35 node p = q.top();36 q.pop();37 int temp = min(s, p.w);38 s -= temp;39 p.w -= temp;40 if (p.w != 0) q.push(p);41 }42 t++;43 if (!q.empty() && q.top().d == t) return false;44 if (q.empty() && cnt == n) return true;45 }46 }47 48 int main()49 {50 ios::sync_with_stdio(false);51 //freopen("D:\\txt.txt", "r", stdin);52 int T;53 cin >> T;54 while (T--)55 {56 cin >> n;57 for (int i = 0; i < n; i++)58 {59 cin >> a[i].r >> a[i].d >> a[i].w;60 }61 sort(a, a + n, cmp);62 int left = 1, right = 100000;63 while (left <= right)64 {65 int mid = (left + right) / 2;66 if (check(mid)) right = mid-1;67 else left = mid + 1;68 }69 cout << left << endl;70 }71 }
LA 4254 处理器（二分+贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。