P9050

ZepX_D · 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;
}