-
通過懸崖的yifenfei,又面臨着幽谷的考驗——
幽谷周圍瘴氣彌漫,靜的可怕,隐約可見地上堆滿了骷髅。由于此處長年不見天日,導緻空氣中布滿了毒素,一旦吸入體内,便會全身潰爛而死。
幸好yifenfei早有防備,提前備好了解藥材料(各種濃度的萬能藥水)。現在隻需按照配置成不同比例的濃度。
現已知yifenfei随身攜帶有n種濃度的萬能藥水,體積V都相同,濃度則分别為Pi%。并且知道,針對當時幽谷的瘴氣情況,隻需選擇部分或者全部的萬能藥水,然後配置出濃度不大于 W%的藥水即可解毒。
現在的問題是:如何配置此藥,能得到最大體積的目前可用的解藥呢?
特别說明:由于幽谷内裝置的限制,隻允許把一種已有的藥全部混入另一種之中(即:不能出現對一種藥隻取它的一部分這樣的操作)。
題目位址:http://ac.jobdu.com/problem.php?pid=1435
題目描述:
- 輸入:
-
輸入資料的第一行是一個整數C,表示測試資料的組數;
每組測試資料包含2行,首先一行給出三個正整數n,V,W(1<=n,V,W<=100);
接着一行是n個整數,表示n種藥水的濃度Pi%(1<=Pi<=100)。
- 輸出:
-
對于每組測試資料,請輸出一個整數和一個浮點數;
其中整數表示解藥的最大體積,浮點數表示解藥的濃度(四舍五入保留2位小數);
如果不能配出滿足要求的的解藥,則請輸出0 0.00。
- 樣例輸入:
-
3 1 100 10 100 2 100 24 20 30 3 100 24 20 20 30
- 樣例輸出:
-
0 0.00 100 0.20 300 0.23
- 提示:
- 如果一直是wa的話。可以參考這個文章:www.cskaoyan.com/viewthread.php
-
相同體積的溶液,濃度越大,混制出來w%濃度,體積越小。
是以需要對溶液濃度大小進行一個排序,如果濃度小,則優先選擇。
首先聲明初始濃度為p = 0,初始體積為allV = 0;
那麼每次混合都需要判斷目前的濃度是否大于w。
由于濃度可能是double類型的資料,判斷起來容易出錯,是以我們反向思考,将除以改成乘以。
遇到不同的問題,可以多方位的思考解決方式。
C++ AC
-
Java AC#include <stdio.h> #include <algorithm> using namespace std; int c,n,v,w; int i; int main(){ while(scanf("%d",&c) != EOF){ while(c > 0){ c--; scanf("%d %d %d",&n,&v,&w); int *array = new int[n]; for (i = 0; i < n; i++) { scanf("%d",&array[i]); } sort(array,array+n); int p = 0; int allV = 0; for (i = 0; i < n; i++) { if ((p + array[i]) > (allV + 1) * w) { break; } p += array[i]; allV ++; } if (allV == 0) { printf("0 0.00\n"); }else { printf("%d %.2f\n",allV*v, p*1.0/(100*allV)); } } } return 0; } /************************************************************** Problem: 1435 User: wangzhenqing Language: C++ Result: Accepted Time:0 ms Memory:1024 kb ****************************************************************/
-
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; public class Main { /* * 1435 */ public static void main(String[] args) throws Exception { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); while (st.nextToken() != StreamTokenizer.TT_EOF) { int c = (int) st.nval; for (int j = 0; j < c; j++) { st.nextToken(); int n = (int) st.nval; st.nextToken(); int v = (int) st.nval; st.nextToken(); int w = (int) st.nval; int array[] = new int[n]; for (int i = 0; i < n; i++) { st.nextToken(); array[i] = (int) st.nval; } Arrays.sort(array); int p = 0; int allV = 0; for (int i = 0; i < n; i++) { if ((p + array[i]) > (allV + 1) * w) { break; } p += array[i]; allV ++; } if (allV == 0) { System.out.println("0 0.00"); }else { System.out.printf("%d %.2f\n",allV*v, p*1.0/(100*allV)); } } } } } /************************************************************** Problem: 1435 User: wzqwsrf Language: Java Result: Accepted Time:80 ms Memory:15184 kb ****************************************************************/