Schedule(Hackerrank Quora Haqathon)
Problem Statement
At Quora, we run all our unit tests across many machines in a test cluster on every code push.
One day, we decided to see if we could optimize our test cluster for cost efficiency by using only one machine to run all N tests.
Suppose we know two things about each test: the time needed to run this test, Ti, and the probability that this test will pass, Pi.
Given these as input, come up with the minimum expected time (based on the optimal ordering of the tests) of getting “go or no go” feedback on the code push, i.e. the expected time when we understand that either i) at least one test has failed, or that ii) all tests have passed.
Constraints
- Accuracy threshold for evaluating floats: 10−6
- 1≤N≤100
- 1≤Ti≤100
- 0≤Pi≤1
Input Format
Line 1: One integer N
Line 2..N+1: One integer Ti and one float Pi separated by one space.
Output Format
Line 1: One float, the minimum expected time
Sample Input
3
3 0.1
7 0.5
9 0.2
Sample Output
4.04
很久之前看的一道题,标签是easy可就是想不到如何做。
问了woshilalala之后,才豁然开朗。对于这种题我就是束手无策。
这种贪心的题目,首先可以假设n = 2. 从而总结出他们之间的关系。然后推广到多个的情况。
附上代码:
#include <cstdio>
#include <algorithm>
using namespace std; int t[], id[];
double p[]; bool cmp(int i, int j) {
return (t[i] * (1.0 - p[j]) < t[j] * (1.0 - p[i]));
} int main(void) {
int N, i;
scanf("%d", &N); for (i = ; i < N; i++) {
scanf("%d %lf", t + i, p + i);
id[i] = i;
} sort(id, id + N, cmp); double ans = 0.0, c = 1.0;
int s = 0.9;
for (i = ; i < N - ; i++) {
s += t[id[i]];
ans += c * ( - p[id[i]]) * s;
c *= p[id[i]];
}
s += t[id[N-]];
ans += c * s; printf("%.17f\n", ans); return ;
}
最新文章
- 安装JBOSS
- od
- HDU 1430 魔板(康托展开+BFS+预处理)
- Data Base MySQL的常用命令
- 原子/Atomic操作
- asp 下拉框二级联动
- Accept 与 Content-Type
- Ubuntu16.04的sublime text3 的安装教程
- 【转】Linux 移动或重命名文件/目录-mv 的10个实用例子
- 注册页面的JSON响应方式详细分析(与前端页面交互方式之一)
- 【Java】【集合】
- Java中static块执行时机
- js实现链式操作
- 在Ubuntu16.04上安装virtualbox后无法装载vboxdrv模块
- loadrunner socket协议问题归纳(2)
- ActionbarActivity和普通的Activity的区别
- 九度OJ 1151:位操作练习 (位操作)
- loj #6079. 「2017 山东一轮集训 Day7」养猫【最大费用最大流】
- 详解Codis安装与部署
- Eclipse添加默认的JRE