hdu 5035 Delivery(概率&分部積分)

Delivery

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 156 Accepted Submission(s): 97


Problem Description Today, Matt goes to delivery a package to Ted. When he arrives at the post office, he finds there are N clerks numbered from 1 to N. All the clerks are busy but there is no one else waiting in line. Matt will go to the first clerk who has finished the service for the current customer. The service time t_i for clerk i is a random variable satisfying distribution p(t_i = t) = k_ie^(-k_it) where e represents the base of natural logarithm and k_i represents the efficiency of clerk i. Besides, accroding to the bulletin board, Matt can know the time c_i which clerk i has already spent on the current customer. Matt wants to know the expected time he needs to wait until finishing his posting given current circumstances.
Input The first line of the input contains an integer T,denoting the number of testcases. Then T test cases follow.

For each test case, the first line contains one integer:N(1<=N<=1000)

The second line contains N real numbers. The i-th real number k_i(0<=k_i<=1) indicates the efficiency of clerk i.

The third line contains N integers. The i-th integer indicates the time c_i(0<=c_i<=1000) which clerk i has already spent on the current customer.
Output For each test case, output one line "Case #x: y", where x is the case number (starting from 1), y is the answer which should be rounded to 6 decimal places.
Sample Input

2
2
0.5 0.4
2 3
3
0.1 0.1 0.1
3 2 5

Sample Output

Case #1: 3.333333
Case #2: 13.333333

Source 2014 ACM/ICPC Asia Regional Beijing Online
Recommend hujie | We have carefully selected several similar problems for you: 5041 5040 5039 5038 5037 題意： 一個人到郵局寄東西。一共有n個工作人員。而每個工作人員前正有一個人正在郵局東西。已知第i工作人員處理一個人的業務用時為t的概率p(t)=ki*e^(-ki*t).現在問你這個人從等待到寄完自己的東西用的時間的期望。 思路： 分部積分。感覺這題考的就是高數。。。 積分公式為(x+y)*ki*e^(-ki*y)*e^(-x*sk)然後x從0積到OO.y再從積到OO公式就出來了。x為等待的時間。y為處理自己事務的時間。sk為所有k的和。積完化簡得.ans=(n+1)/sk. 然後代碼就很簡單了。。。。 詳細見代碼:

#include
#include
#include
#include
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;

int main()
{
    int t,cas=1,n,c,i;
    double k,sk;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        sk=0;
        for(i=1;i<=n;i++)
        {
            scanf("%lf",&k);
            sk+=k;
        }
        for(i=1;i<=n;i++)
            scanf("%d",&c);
        printf("Case #%d: %.6f\n",cas++,(n+1)/sk);
    }
    return 0;
}