H – 【59】Lazier Salesgirl 模拟//lxm

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

2
4
1 2 3 4
1 3 6 10
4
4 3 2 1
1 3 6 10

Sample Output

4.000000 2.500000
1.000000 4.000000题意是要求出时间w使得卖出面包的平均价格最大
这个题可以求出到第i个客服保持清醒的时间w[i]然后模拟一遍就可

#include <iostream>#include <stdio.h>#include <cmath>using namespace std;#define maxn 1111int p[maxn], times[maxn], w[maxn];int t,n;int main(){    cin>>t;    while(t--)    {        cin>>n;        for(int i=;i<n;i++)            cin>>p[i];        for(int i=;i<n;i++)            cin>>times[i];        w[]=times[];        for(int i=;i<n;i++)            w[i]=max(times[i]-times[i-],w[i-]);//到第i个所需要的最大的时间        double the_time=,sum,ave,time;        ave=;        for(int i=;i<n;i++)        {            time=w[i];            sum=;            int cnt=;            for(int j=;j<n;j++)            {                if(time>=w[j])                {                    sum+=p[j];                    cnt++;                }                else                    break;            }            if(ave<sum/cnt)            {                ave=sum/cnt;                the_time=time;            }            else if (ave==sum/cnt)            {                the_time=min(the_time,time);            }        }        printf("%.6lf %.6lf\n",the_time,ave);    }    return ;}