\(\mathcal{Description}\)

有 \(n\) 个人掉进了深度为 \(h\) 的坑里，第 \(i\) 个人的肩高为 \(a_i\)，臂长为 \(b_i\)。设当前坑里人的集合为 \(S\)，第 \(i\) 人能逃生，当且仅当 \(\sum_{j\in S}a_j+b_i\ge h\)。求最多逃生人数。

\(n\le2\times10^5\)。

\(\mathcal{Solution}\)

考虑在最优情况下，相邻两个逃生的人，设其肩高臂长分别为 \((a,b),(p,q)\)，未逃生者肩高之和 \(s\)，则现在有：

\[\begin{cases}
s+b\ge h\\
s-a+q\ge h
\end{cases}
\]

尝试交换两人顺序：

\[\begin{cases}
s+q\ge h\\
s-p+b\ge h
\end{cases}
\]

不难发现 \(b-p\le q-a\) 时，前式可推出后时，可结合题意理解为“前者逃生，考虑为后者手变短，那么后者手越长越优”。依此排序。

此后，顺序扫一遍，若当前人能逃生直接逃生。但为保证最优，我们需要最大化坑里人的 \(\sum a_i\)。这时考虑一个反悔操作——用逃生的一个人来替换当前这个人。显然由于贪心的排序，替换一定成立，只要逃生的人的肩高大于当前人，替换就会优化答案，所以直接抓肩高最大的人回坑里就好。

复杂度 \(\mathcal O(n\log n)\)。

\(\mathcal{Code}\)

#include <queue>

#include <cstdio>

#include <algorithm> 

typedef long long LL;

inline int rint () {

	int x = 0; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () );

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x;

}

const int MAXN = 2e5;

int n, H;

LL sum;

std::priority_queue<int> heap;

struct Person {

	int a, b;

	inline void read () { a = rint (), b = rint (); }

	inline bool operator < ( const Person t ) const { return b - t.a < t.b - a; }

} per[MAXN + 5];

int main () {

	freopen ( "escape.in", "r", stdin );

	freopen ( "escape.out", "w", stdout );

	n = rint ();

	for ( int i = 1; i <= n; ++ i ) per[i].read (), sum += per[i].a;

	H = rint ();

	int ans = 0;

	std::sort ( per + 1, per + n + 1 );

	for ( int i = 1; i <= n; ++ i ) {

		heap.push ( per[i].a );

		if ( sum + per[i].b >= H ) ++ ans;

		else sum += heap.top (), heap.pop ();

		sum -= per[i].a;

	}

	printf ( "%d\n", ans );

	return 0;

}

\(\mathcal{Details}\)

也是够勇的，不拍就过了这道智慧贪心题 owo！

巴特西

Solution -「LOCAL」逃生

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

\(\mathcal{Details}\)

最新文章

热门文章