ZOJ 3607 Lazier Salesgirl（贪心）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 1000+10;
 8 const int INF = 1<<28;
 9 int p[maxn], t[maxn];
10 
11 int main()
12 {
13     int i, j, T, n;
14     double sum, ty, tty;
15     double Maxaver, x, Mint;
16     while(~scanf("%d", &T))
17     {
18         while(T--)
19         {
20             Maxaver = -INF;
21             tty = -INF;
22             Mint = INF;
23             sum = 0;
24             scanf("%d", &n);
25             for(i = 1; i <= n; i++)
26             scanf("%d", &p[i]);
27             for(j = 1; j <= n; j++)
28             scanf("%d", &t[j]);
29 
30             t[n+1] = INF;   //初始一个最大值
31             for(i = 1; i <= n; i++)
32             {
33                 ty = t[i] - t[i-1];
34                 if(ty > tty)
35                 tty = ty;
36                 sum+=p[i];
37                 x = sum*1.0/i*1.0;
38                 if(x > Maxaver && t[i+1]-t[i]>tty)
39                 {
40                     Mint = tty;
41                     Maxaver = x;
42                 }
43             }
44             printf("%.6lf %.6lf\n", Mint, Maxaver);
45         }
46     }
47     return 0;
48 }