自动搬运

查看原文

来自洛谷，原作者为

	ZepX_D 12.20

搬运于2025-08-24 22:44:56，当前版本为作者最后更新于2023-02-08 20:44:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

一条鱼最优的情况肯定是要把能吃的都吃了，因为吃别的鱼能获得更大的收益，但每条鱼都枚举一遍 $O(n^2)$ 的复杂度肯定是过不了的，发现假如一条鱼能活到最后，那比它重的必然能活到最后，且比它轻的必然活不到最后，满足单调性，所以我们可以先排序后二分，每次模拟一遍看能否活到最后就行，复杂度 $O(n \log n)$。

代码

#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

inline ll read()
{
	ll x = 0;char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
	return x;
}

struct fish
{
	ll w,id;
}a[500010];
int n;
char ans[500010];
queue < ll > q;

bool cmp(fish x,fish y)
{return x.w < y.w;}

bool check(int k)
{
	while(!q.empty()) q.pop();
	for (int i = 1;i <= n;i++)
		if (i != k) q.push(a[i].w);
	ll s = a[k].w;
	while (!q.empty())
	{
		if (q.front() >= s) return 0;
		s += q.front();q.pop();
	}
	return 1;
}

int main()
{
	n = read();
	for (int i = 1;i <= n;i++)
		a[i].w = read(),a[i].id = i;
	sort(a+1,a+n+1,cmp);
	int l = 1,r = n+1;
	while(l < r)
	{
		int mid = (l+r)>>1;
		if (check(mid)) r = mid;
		else l = mid+1;
	}
	if (l > n) for (int i = 1;i <= n;i++) putchar('N');
	else 
	{
		for (int i = 1;i <= n;i++)
			ans[a[i].id] = (a[i].w >= a[l].w?'T':'N');
		for (int i = 1;i <= n;i++)
			printf("%c",ans[i]);
	}
	return 0;
}