题解：P10730 [NOISG 2023 Qualification] Burgers

题意：给定数组

a,b,c

，求两个整数使得

x+y

最大且满足

\forall 1 \leq i \leq n,xa_i + yb_i \leq c_i

。

给这个式子换个形式：

y \leq \frac{c_i-xa_i}{b_i}

。

得到

x+y \leq (1-\frac{a_i}{b_i})x + \frac{c_i}{b_i}

。

发现这相当于给一些线段，求线段下方最大点。

建出凸包简单维护即可。

Code

CPP

#include <bits/stdc++.h>
using namespace std;

inline long long read(void) {
	long long x = 0, f = 1; char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - 48, c = getchar();
	return x * f;
}

struct node {
	long double k, b, bg;
} stk[100005];

struct line {
	long double k, b;
	friend bool operator< (line x, line y) {
		if (x. k == y. k) return x. b < y. b;
		return x. k > y. k;
	}
} lne[100005];

long long n, cnt, cct, c[100005], a[100005], b[100005], ans;

int main(void) {
	n = read();
	for (int i = 1; i <= n; i++) c[i] = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= n; i++) b[i] = read();
	if (a[1] < b[1]) for (int i = 1; i <= n; i++) swap(a[i], b[i]);
	for (int i = 1; i <= n; i++) lne[i]. k = (long double)1 - (long double)(a[i]) / b[i], lne[i]. b = (long double)c[i] / b[i];
	sort(lne + 1, lne + 1 + n);
	for (int i = 1; i <= n; i++)
		if (i == 1 || lne[i]. k != lne[i - 1]. k)
			lne[++cct] = lne[i];
	n = cct;
	stk[++cnt] = {lne[1]. k, lne[1]. b, 0};
	for (int i = 2; i <= n; i++) {
		while (cnt && (lne[i]. b - stk[cnt]. b) / (stk[cnt]. k - lne[i]. k) <= stk[cnt]. bg) cnt--;
		if (!cnt) stk[++cnt] = {lne[i]. k, lne[i]. b, 0};
		else cnt++, stk[cnt] = {lne[i]. k, lne[i]. b, (lne[i]. b - stk[cnt - 1]. b) / (stk[cnt - 1]. k - lne[i]. k)};
	}
	for (int i = 1; i <= cnt; i++) {
		if (i == cnt || ceill(stk[i]. bg) < stk[i + 1]. bg) ans = max(ans, (long long)(ceill(stk[i]. bg) * stk[i]. k + stk[i]. b));
		if (i < cnt && floor(stk[i + 1]. bg) >= stk[i]. bg) ans = max(ans, (long long)((floor(stk[i + 1]. bg)) * stk[i]. k + stk[i]. b));
	}
	printf("%lld", ans);
	return 0;
}

题解：P10730 [NOISG 2023 Qualification] Burgers

文章操作

相关推荐

评论

题解：P10730 [NOISG 2023 Qualification] Burgers