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

33 0.17 0.59 0.2

Sample Output

4.04

很久之前看的一道题，标签是easy可就是想不到如何做。

问了woshilalala之后，才豁然开朗。对于这种题我就是束手无策。

这种贪心的题目，首先可以假设n = 2. 从而总结出他们之间的关系。然后推广到多个的情况。

附上代码：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 int t[100], id[100]; 6 double p[100]; 7  8 bool cmp(int i, int j) { 9     return (t[i] * (1.0 - p[j]) < t[j] * (1.0 - p[i]));10 }11 12 int main(void) {13     int N, i;14     scanf("%d", &N);15 16     for (i = 0; i < N; i++) {17             scanf("%d %lf", t + i, p + i);18             id[i] = i;19     }20 21     sort(id, id + N, cmp);22 23     double ans = 0.0, c = 1.0;24     int s = 0.9;25     for (i = 0; i < N - 1; i++) {26         s += t[id[i]];27         ans += c * (1 - p[id[i]]) * s;28         c *= p[id[i]];29     }30     s += t[id[N-1]];31     ans += c * s;32 33     printf("%.17f\n", ans);34 35     return 0;36 }