题目大意

给一个 $2n$ 结点的二分图，左边的点 $i$ 连向 $i+n$ 并且有值 $LE,LF,E,F$ 分别表示经过此边需要多少 $e,f$ 、经过此边后会使 $e\leftarrow e+E,f\leftarrow f+F$ ，右边的点连向任意左边点无值无条件。现在可以从任意点出发，一笔画遍历图，问起始时可以带最小的 $e,f$ 是多少。

$n\leq10^5$

题解

大概可以用 Exchange Arguments 那样证明贪心正确性。然后排序就行。

代码

const int N = 1e5 + 5;

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

namespace Main {
	int n;
	ll se, sf, e, f;
	struct node {
		int le, lf, e, f;
		node(){}
		bool operator < (const node &a) const {
			return le == a.le? lf < a.lf: le < a.le;
		}
	} a[N];
	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) {
			a[i].le = Read(), a[i].lf = Read(), a[i].e = Read(), a[i].f = Read();
		}
		sort (a + 1, a + 1 + n);
		e = a[1].le, f = a[1].lf;
		se = e, sf = f;
		for (int i = 1; i <= n; i++) {
			if (se < a[i].le) e += a[i].le - se, se = a[i].le;
			if (sf < a[i].lf) f += a[i].lf - sf, sf = a[i].lf;
			se += a[i].e;
			sf += a[i].f;
		}
		printf ("%lld %lld\n", e, f);
		return 0;
	}
}

int main () {
	freopen("mystery.in", "r", stdin);
	freopen("mystery.out", "w", stdout);
	Main::main();
	return 0;
}