首页 > 代码库 > H - Lazier Salesgirl
H - Lazier Salesgirl
Description
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 pi. 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 ti 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 ≤ pi ≤ 10000. The third line contains n integers 1 ≤ ti ≤ 100000. The customers are given in the non-decreasing order of ti.
Output
For each test cases, output w and the corresponding average value of sold bread, with six decimal digits.
Sample Input
241 2 3 41 3 6 1044 3 2 11 3 6 10
Sample Output
4.000000 2.5000001.000000 4.000000
题目大意就是一个买面包的小姑凉想偷懒，在卖到第i个人的时候，就会在一个之前维持的最大间隔时间内（如果在这个时间内没人来买面包的）她会一睡不醒。但又要满足能否去到最大平均值。
总体来说，这道题有两个条件：平均值最大，并且能一睡不醒。
1 #include<cstdio> 2 #include<string.h> 3 using namespace std; 4 double p[1010]; 5 double time[1010]; 6 double maxt[1010]; 7 double max(double a,double b) 8 { 9 return a>b?a:b;10 }11 int main()12 {13 int t,n;14 double w;15 double flag;16 scanf("%d",&t);17 while(t--)18 {19 scanf("%d",&n);20 for(int i=1;i<=n;i++)21 scanf("%lf",&p[i]);22 for(int i=1;i<=n;i++)23 scanf("%lf",&time[i]);24 time[0]=0;25 maxt[1]=time[1]-time[0];26 for(int i=2;i<=n;i++)27 maxt[i]=max(time[i]-time[i-1],maxt[i-1]);//算出到第i个人时的前面的最大间隔时间28 double maxn=0;//最大平均值29 double anst=0;//间隔时间30 double sum=0;31 for(int i=1;i<=n;i++)//暴力枚举32 {33 w=maxt[i];34 sum+=p[i];35 if(i==n)36 {37 if(sum/i>maxn)38 {39 maxn=sum/i;40 flag=w;41 break;42 }43 }44 if(sum/i>maxn&&w<time[i+1]-time[i])//要保证他卖给第i个人后能睡觉45 {46 maxn=sum/i;47 flag=w;48 }49 50 }51 printf("%.6lf %.6lf\n",flag,maxn);52 }53 return 0;54 }