題目:
5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1Sample Output
13.333 31.500AuthorCHEN, Yue SourceZJCPC2004 RecommendJGShining
題目大意:
老鼠准備了M磅貓食,准備拿這些貓食跟貓交換自己喜歡的食物。有N個房間,每個房間裡面都有食物。你可以得到J[i]但你需要付出F[i]的貓食。要你計算你有M磅貓食可以獲得最多食物的重量。而且這裡可以不必每一組都全換,可以按比例換。。。例如最後你只剩5塊錢貓食。但是目前的一個選擇是話10塊貓食就能換取6個糧食。那麼這時候你用5塊貓食就能換取3個糧食
題目分析:
這是一道簡單的貪心題。對於這種獲得收入的同時需要付出一些的情況下,計算最大收入。這種題一般是根據
收入和付出的比例來排一下序。然後根據這個比例從高到低進行選擇
代碼如下:
/* * a.cpp * * Created on: 2015年1月28日 * Author: Administrator */ #include#include #include using namespace std; const int maxn = 10005; struct W { double get;//收入 double pay;//付出的貓食 double ave;//收入/付出比 } w[maxn]; bool cmp(W a, W b) { if (a.ave > b.ave) { return true; } return false; } int main() { int n; double m; while (scanf("%lf%d", &m, &n), n != -1 && m != -1) { int i; for (i = 0; i < n; ++i) { scanf("%lf %lf", &w[i].get, &w[i].pay); w[i].ave = w[i].get / w[i].pay; } sort(w, w + n, cmp);//貪心,對w按照get/pay進行降序排序 double sum = 0; i = 0; // while(m >= 0){//不知道為什麼這種寫法就是不行. // if (m >= w[i].pay) { // sum = sum + w[i].get; // m = m - w[i].pay; // } else { // sum = sum + w[i].ave * m; // break; // } // i++; // } for (i = 0; i <= n - 1; i++) { if (m >= w[i].pay) {//如果當前剩余的貓食還足夠的話 sum = sum + w[i].get;//那就把那個房間的糧食全部買下 m = m - w[i].pay;//並且手上見去相應的貓食 } else {//如果現在手上的貓食已經不夠 sum = sum + w[i].ave * m;//那麼就按比例拿去一定的貓食 break; } } printf("%.3lf\n", sum); } return 0; }