ZOJ3068（01分数规划）

本是POJ2976，喜闻乐见的01规划入门题。POJ日常假死，到ZOJ测。

二分答案。

试了试数据好像没问题，\(a_i\)总是小于\(b_i\)且最终预答案l都小于1。然而为什么我把r设成1e10往上就会WA，设成1或者1e3会AC，设成1e2会WA……而且网上题解基本都会被全0的数据hack啊……求解答

#include <cstdio>

#include <cctype>

#include <algorithm>

#define mset(a, b) memset(a, b, sizeof(a))

#define rep(i, a, b) for (int i = a; i <= b; i++)

#define per(i, a, b) for (int i = a; i >= b; i--)

#define fg cout << "--------------\n";

#define debug(x) std::cerr << #x << " = " << x << std::endl

#define All(x) (x.begin()), (x.end())

using namespace std;

typedef double db;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll INF = 1e18;

template <typename T> void read(T &x) {

	x = 0;

	int s = 1, c = getchar();

	for (; !isdigit(c); c = getchar())

		if (c == '-')	s = -1;

	for (; isdigit(c); c = getchar())

		x = x * 10 + c - 48;

	x *= s;

}

template <typename T> void write(T x) {

	if (x < 0)	x = -x, putchar('-');

	if (x > 9)	write(x / 10);

	putchar(x % 10 + '0');

}

template <typename T> void writeln(T x) {

	write(x);

	puts("");

}

const int maxn = 1e3 + 5;

const db eps = 1e-4;

int n, k;

db a[maxn], b[maxn], c[maxn];

bool not_ok(db mid) {

	db res = 0;

	rep(i, 1, n)	c[i] = a[i] - b[i] * mid, res += c[i];

	sort(c + 1, c + 1 + n);

	rep(i, 1, k)	res -= c[i];

	return res < 0;

}

int main() {

	while (~scanf("%d %d", &n, &k) && (n | k)) {

		db x = 0;

		rep(i, 1, n)	read(a[i]), x += a[i];

		rep(i, 1, n)	read(b[i]);

		if (x == 0.0) {

			puts("0"); continue;

		}

		db l = 0, r = 1;

		while (r - l > eps) {

			db mid = (l + r) / 2.0;

			if (not_ok(mid))	r = mid;

			else	l = mid;

		}

		printf("%.0lf\n", l * 100.0);

	}

	return 0;

}

巴特西

ZOJ3068（01分数规划）

最新文章

热门文章