HDU 2570 迷瘴

题目链接：HDU 2570【迷障】

思路

       简单贪心，需要算出尽可能大的体积，所以先将浓度数组按从小到大的顺序排列，然后从小到大依次取出药水配置，直到浓度大于w，回溯到前一个状态并输出

代码

#include <bits/stdc++.h>
#include <exception>
using namespace std;
#define ll long long
const int N = 1e5 + 10;

double p[N];
int n, v;
double w;
int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> v >> w;
    int dv = 0;
    double dw = 0;
    for (int i = 1; i <= n; i++) {
      cin >> p[i];
    }
    sort(p + 1, p + 1 + n);
    for (int i = 1; i <= n; i++) {
      int ddv = dv;
      double ddw = dw;
      ddw = (ddv * ddw + v * p[i]) / (ddv + v);
      ddv += v;
      if (ddw > w) {
        break;
      }
      dv = ddv, dw = ddw;
    }
    printf("%d %.2f\n", dv, dw / 100);
  }

  return 0;
}