HDU 4957 Poor Mitsui

题目链接

思路：利用相邻交换法去贪心即可，注意容积为0的情况，这是个坑点

代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int N = 45; struct SB { int a, b; } sb[N]; bool cmp(SB x, SB y) { return x.b * y.a < x.a * y.b; } int t, n, v; double solve() { for (int i = 0; i < n; i++) if (sb[i].b && sb[i].a >= v) return -1; double ans = 0; for (int i = 0; i < n; i++) { if (sb[i].b == 0) continue; ans = ans + (sb[i].b + sb[i].a * ans) / (v - sb[i].a); } return ans; } int main() { scanf("%d", &t); while (t--) { scanf("%d%d", &n, &v); for (int i = 0; i < n; i++) scanf("%d", &sb[i].a); for (int i = 0; i < n; i++) scanf("%d", &sb[i].b); sort(sb, sb + n, cmp); printf("%.0f\n", solve()); } return 0; }