题解：P14660 你不孤单，我们都在

· · 题解

最多操作一次，所以所有不合法的人都需要参与活动。

我们不妨先把他们全部扔进来。

然后平均数一定要小于所有参与活动的人的 b 最小值。

于是考虑反悔贪心。

我们按照 b 降序排序。

然后把 a 插到优先队列里面，如果会使平均数变大就不插了。

插完我们把队头那些会使平均数变大的点踢出去。

动态维护这个过程的平均数，显然对于每一个 b 作为最小值时都达到了最优。于是这个贪心是对的。

如果存在某一时刻能够满足条件，那么就直接返回 YES，否则返回 NO。

做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct fish{
    int a,b;
}a[100005];
bool cmpb(fish x,fish y){
    return x.b>y.b;
}
void solve(){
    int n;
    cin>>n;
    int sum=0,cnt=0,qwq=1e9;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
        if(a[i].a>a[i].b)
        sum+=a[i].a,cnt++,qwq=min(qwq,a[i].b);
    }
    sort(a+1,a+1+n,cmpb);
    priority_queue<int>q;
    for(int i=1;i<=n;i++){
        if(a[i].a>a[i].b)continue;
        if((sum+a[i].a)*cnt>sum*(cnt+1))continue;
        qwq=min(qwq,a[i].b);
        sum+=a[i].a;
        cnt++;
        q.push(a[i].a);
        while(cnt>1&&(sum-q.top())*cnt<sum*(cnt-1)){
            cnt--;
            sum-=q.top();
            q.pop();
        }
        if(sum<=qwq*cnt){
            puts("YES");
            return;
        }
    }
    puts("NO");
}
signed main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 起初，缇亚忒只是觉得那好厉害。
// 缇亚忒一直仰望着那道让她觉得帅气而耀眼的背影。她怀有憧憬。

// 后来，当缇亚忒自己的手脚开始成长时，那份憧憬变成了希望。自己迟早会前往战场。到时候，她肯定会跟那位珂朵莉学姐一样，变成既杰出又帅气，而且最顶尖也最强的妖精。