迷瘴 - 武林網

迷瘴

2019-11-11 03:29:45

字體：大中小

來源：轉載

供稿：網友

PRoblem Description

通過懸崖的yifenfei，又面臨著幽谷的考驗——幽谷周圍瘴氣彌漫，靜的可怕，隱約可見地上堆滿了骷髏。由于此處長年不見天日，導致空氣中布滿了毒素，一旦吸入體內，便會全身潰爛而死。幸好yifenfei早有防備，提前備好了解藥材料（各種濃度的萬能藥水）?，F在只需按照配置成不同比例的濃度。現已知yifenfei隨身攜帶有n種濃度的萬能藥水，體積V都相同，濃度則分別為Pi%。并且知道，針對當時幽谷的瘴氣情況，只需選擇部分或者全部的萬能藥水，然后配置出濃度不大于 W%的藥水即可解毒?，F在的問題是：如何配置此藥，能得到最大體積的當前可用的解藥呢？特別說明：由于幽谷內設備的限制,只允許把一種已有的藥全部混入另一種之中（即：不能出現對一種藥只取它的一部分這樣的操作）。

提示：多種藥水混合后的濃度=(濃度1*體積1+濃度2*體積2+……)/(體積和)

Input

輸入數據的第一行是一個整數C，表示測試數據的組數；每組測試數據包含2行，首先一行給出三個正整數n,V,W(1<=n,V,W<=100)；接著一行是n個整數，表示n種藥水的濃度Pi%(1<=Pi<=100)。

Output

對于每組測試數據，請輸出一個整數和一個浮點數；其中整數表示解藥的最大體積，浮點數表示解藥的濃度(四舍五入保留2位小數)；如果不能配出滿足要求的的解藥，則請輸出0 0.00。

Example Input

31 100 101002 100 2420 303 100 2420 20 30Example Output
0 0.00100 0.20300 0.23Hint
hdoj2570Author
01 #include<stdio.h>
02 struct yao
03 {
04     int n, v, w;
05     int p[101];
06 } a[10000];
07 int main()
08 {
09     int T, i, j, k, V, flag, t;
10     double d, d2;
11     scanf("%d", &T);
12     for(i = 0; i < T; i++)
13     {
14         scanf("%d%d%d", &a[i].n, &a[i].v, &a[i].w);
15         for(j = 0; j < a[i].n; j++)
16             scanf("%d", &a[i].p[j]);
17         for(j = 0; j < a[i].n - 1; j++)
18         {
19             for(k = j + 1; k < a[i].n; k++)
20             {
21                 if(a[i].p[j] > a[i].p[k])
22                 {
23                     t = a[i].p[j];
24                     a[i].p[j] = a[i].p[k];
25                     a[i].p[k] = t;
26                 }
27             }
28         }
29         if(a[i].p[0] > a[i].w) printf("0 0.00/n");
30         else
31         {
32             d = a[i].p[0] * 0.01;
33             V = a[i].v;
34             flag = 0;
35             for(j = 1; j < a[i].n; j++)
36             {
37                 d2 = d;
38                 d = (d * V + a[i].p[j] * a[i]. v * 0.01) / (V + a[i].v);
39                 V = V + a[i].v;
40                 if(d > a[i].w * 0.01)
41                 {
42                     flag = 1;
43                     break;
44                 }
45             }
46             if(flag) printf("%d %.2lf/n", V - a[i].v, d2);
47             else printf("%d %.2lf/n", V, d);
48         }
49     }
50     return 0;
51 }