ZOJ 3607贪心算法

http://blog.csdn.net/ffq5050139/article/details/7832991

http://blog.watashi.ws/1944/the-8th-zjpcpc/

http://blog.csdn.net/crescent__moon/article/details/16801097

 #include<cstdio>

 #include<cstring>

 const int Max=;

 double t[Max],p[Max],lev[Max];

 double max(double a,double b){

     return a>b?a:b;

 }

 int main(){

     int i,j,n,T;

     double sum,ans,anst,w;

     scanf("%d",&T);

     while(T--){

         sum=ans=anst=;

         scanf("%d",&n);

         for(i=;i<n;i++)

             scanf("%lf",&p[i]);

         for(i=;i<n;i++)

             scanf("%lf",&t[i]);

         lev[]=t[];

         //printf("lev[1] = %.6lf\n",lev[0]);

         for(i=;i<n;i++){

             lev[i]=max(t[i]-t[i-],lev[i-]);

         }

         for(i=;i<n;i++){

             w=lev[i];

             sum=;

             for(j=;j<n;j++){

                 if(w >= lev[j])

                     sum += p[j];

                 else

                     break;

             }

             if(ans < sum / j){

                 ans=sum/j;

                 anst=w;

             }

         }

         printf("%.6lf %.6lf\n",anst,ans);

     }

     return ;

 }

Lazier Salesgirl

Time Limit: 2 Seconds Memory Limit: 65536 KB

Kochiya Sanae is a lazy girl who makes and sells bread. She is an expert at bread making and selling. She can sell the i-th customer a piece of bread for price p_i. But she is so lazy that she will fall asleep if no customer comes to buy bread for more than w minutes. When she is sleeping, the customer coming to buy bread will leave immediately. It's known that she starts to sell bread now and the i-th customer come after t_i minutes. What is the minimum possible value of w that maximizes the average value of the bread sold?

Input

There are multiple test cases. The first line of input is an integer T ≈ 200 indicating the number of test cases.

The first line of each test case contains an integer 1 ≤ n ≤ 1000 indicating the number of customers. The second line contains n integers 1 ≤ p_i ≤ 10000. The third line contains n integers 1 ≤ t_i ≤ 100000. The customers are given in the non-decreasing order of t_i.

Output

For each test cases, output w and the corresponding average value of sold bread, with six decimal digits.

Sample Input

Sample Output

4.000000 2.500000

1.000000 4.000000

巴特西

ZOJ 3607贪心算法

Input

Output

Sample Input

Sample Output

最新文章

热门文章