HDU 4952 Poor Mitsui（貪心)

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;
}