编辑
2023-10-21
数据结构与算法
00
请注意,本文编写于 615 天前,最后修改于 615 天前,其中某些信息可能已经过时。

任务不会消耗时间,这是一个贪心题目,首先肯定会想到,完成任务并不会消耗时间,但你的时间得大于所需时间。

首先肯定是先完成b更大的因为能获得的时间更多之后能完成的任务也更多,但是所有都按b从大到小排序

做完b大于0的任务后,T=10,剩下2组任务:t1=9,b1=-5;t2=4,b2=-2;显然如果先做第二个的话,会使得第一个任务不能完成

我们可以这样想:对于两组任务t1、b1、t2、b2(其中b1、b2全为负)且当时的时间为T,若先做第一个任务会使得不能做第二个任务而先做第二个任务后还能继续完成第一个任务,则会有

T+b1<t2,T+b2>t1;

移项可得

T<t2-b1,T>t1-b2;

根据不等式的传递性可知

t1-b2<T<t2-b1即t1+b1<t2+b2;

所以我们可以看出按照b+t从大到小的顺序排序可使得答案最优

cpp
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Task { int t; int b; Task(int time, int bonus) : t(time), b(bonus) {} }; bool comparePositive(const Task& a, const Task& b) { return a.t < b.t; // Sort positive bonus tasks by time } bool compareNegative(const Task& a, const Task& b) { return (a.t + a.b) > (b.t + b.b); // Sort negative bonus tasks by (time + bonus) } int main() { int Z; cin >> Z; while (Z--) { int n, T; cin >> n >> T; vector<Task> positive; vector<Task> negative; for (int i = 0; i < n; i++) { int t, b; cin >> t >> b; Task task(t, b); if (b > 0) { positive.push_back(task); } else { negative.push_back(task); } } sort(positive.begin(), positive.end(), comparePositive); sort(negative.begin(), negative.end(), compareNegative); bool success = true; for (const Task& task : positive) { if (T > task.t) { T += task.b; } else { success = false; break; } } for (const Task& task : negative) { if (T > task.t) { T += task.b; } else { success = false; break; } if (T <= 0) { success = false; break; } } if (success) { cout << "+1s" << endl; } else { cout << "-1s" << endl; } } return 0; }

本文作者:yowayimono

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!