x****c
发帖数: 18 | 1 一道新题，但完全没看懂题意是什么，高人给解答下？
1465. Order Of Tasks
Description
Notes
Testcase
Judge
Discuss
There are n different tasks, the execution time of tasks are t[], and the
probability of success are p[]. When a task is completed or all tasks fail,
the operation ends. Tasks are performed in a different order, and it is
expected that the time to stop the action is generally different. Please
answer in what order to perform the task in order to make the end of the
expected action the shortest time? If the expected end time of the two task
sequences is the same, the lexicographic minimum order of tasks is returned.
Notice
$1 leq n leq 50, 1 leq t_i leq 10, 0 leq p_i leq 1$
$n$ is a positive integer, $t_i$ is a positive integer, $p_i$ is a floating-
point number
Have you met this question in a real interview? Yes
Example
Given n=1, t=[1], p=[1.0], return [1].
Explanation:
The shortest expected action end time is 1.0*1+(1.0-1.0)*1=1.0
Given n=2, t=[1,2], p=[0.3, 0.7], return [2,1].
Explanation:
The shortest expected action end time is 0.7*2+(1.0-0.7)*0.3*(2+1)+(1.0-0.7)
*(1.0-0.3)*(2+1)=2.3
贴一个别人写的代码：
class Solution {
public:
/**
* @param n: The number of tasks
* @param t: The time array t
* @param p: The probability array p
* @return: Return the order
*/
struct node
{
int id, t;
double p;
node()
{}
node(int id, int t, double p) : id(id), t(t), p(p)
{}
};
static bool comp(node &l, node &r)
{
return l.p * r.t > r.p * l.t || abs(l.p * r.t - r.p * l.t) < 1e-4 &&
l.id < r.id;
}
vector getOrder(int n, vector &t, vector &p) {
// Write your code here
vector a(n);
for(int i = 0; i < n; i++)
a[i] = node(i + 1, t[i], p[i]);
sort(a.begin(), a.end(), comp);
vector res;
for(auto &it: a)
res.push_back(it.id);
return res;
}
}; |
|
