题解：P14660 你不孤单，我们都在
_jianghaochen_
·
·
题解
更好的阅读体验
题意
我们有 n 个朋友，每个朋友有：
当前压力值 a_i。
最大承受值 b_i。
我们可以选择至多一次倾诉活动：
选择任意一些人参加。
所有被选中的人的压力值会变成 这些人的压力值的平均值。
目标：活动后，所有人满足 a_i \leq b_i。
关键转化
如果不做活动，那么要求：\forall i, a_i \leq b_i。
如果已经满足，那么直接输出 YES。
如果有一些人不满足（即 a_i > b_i），那么必须通过一次活动来尝试解决。
设参加活动的人的集合为 S，人数为 |S|，原来压力值总和为 sum_S，那么活动后，这些人的压力值都变为：
如果 $a_i > b_i$，那么这个人 必须 参加活动，因为如果不参加，他仍然 $a_i > b_i$，不可能满足条件。
设必须参加的人集合为 $M$，$sum_M$ 为他们的压力值之和，$|M|$ 为人数。
活动后，对于参加的人：
$\frac{sum_S}{|S|} \leq \min b_i$。
因为参加的人压力值都变成平均值，要满足每个人的 $b_i$ 限制，必须平均值 $\leq$ 每个人最小 $b_i$ 值。
对于不参加的人：
$a_i \leq b_i
这本来就是 a_i \leq b_i 的人，活动前就满足。
我们已知：
可以从 $a_i \leq b_i$ 的人中选一些人加入活动，记为集合 $O$。
设 $O$ 的 $a$ 总和为 $sum_O$，人数为 $|O|$。
条件：
$\frac{sum_M + sum_O}{|M| + |O|} \leq \min b_i$。
设 $B_{min} = \min_{i \in S} b_i$，则条件等价于：
$sum_M + sum_O \leq B_{min} \times (|M| + |O|)$。
整理得：
$sum_M - B_{min} \times |M| \leq \sum (B_{min} - a_i)$。
由于 $M$ 中每个人 $a_i > b_i \geq B_{min}$（因为 $B_{min}$ 是 $S$ 中最小的 $b_i$），所以左边是负数，更容易满足。
## 贪心策略
为了最大化右边 $\sum (B_{min} - a_i)$，我们应该选择那些 $a_i \leq B_{min}$ 且 $a_i \leq b_i$ 的人加入 $O$，且 $a_i$ 越小越好（因为 $B_{min} - a_i$ 越大）。
## 算法步骤：
把所有人分为两类：
必须参加的人 $M$：$a_i > b_i$。
可选的人 $O$：$a_i \leq b_i$。
如果没有必须参加的人，直接输出 YES。
对可选的人按 $b_i$ 从大到小排序。
遍历所有可能的 $B_{min}$ 值（来自 $M$ 和 $O$ 的 $b_i$）。
对于每个 $B_{min}$，选择所有 $b_i \geq B_{min}$ 的可选人，且只选那些 $a_i \leq B_{min}$ 的（否则平均值可能超过 $B_{min}$）。
检查平均值条件是否满足。
## 数据结构优化
直接遍历 $O(n^2)$ 会超时，需要优化：
用树状数组维护可选人的 $a_i$ 值。
对 $b_i$ 从大到小扫描，动态加入可选人。
快速查询 $a_i \leq B_{min}$ 的可选人的个数和 $a_i$ 总和。
时间复杂度：$O(n \log n)$。
## 代码
```cpp
#include <bits/stdc++.h>
#define Code using
#define by namespace
#define jhc std
Code by jhc;
typedef long long ll;
const int N = 100005;
pair<ll , ll> must[N] , opt[N];
ll all_a[N] , all_b[N];
int bit_cnt[N];
ll bit_sum[N];
int n , m;
//树状数组
void update(int idx , ll val)
{
for(int i = idx;i <= m;i += i & -i)
{
bit_cnt[i]++;
bit_sum[i] += val;
}
}
ll q_cnt , q_sum;
void query(int idx)
{
q_cnt = 0 , q_sum = 0;
for(int i = idx;i > 0;i -= i & -i)
{
q_cnt += bit_cnt[i];
q_sum += bit_sum[i];
}
}
bool solve()
{
int n;
scanf("%d" , &n);
int must_cnt = 0 , opt_cnt = 0;
ll sumM = 0 , cntM = 0 , minB_M = 1e18;
for(int i = 0;i < n;i++)
{
ll a , b;
scanf("%lld %lld" , &a , &b);
if(a > b)
{
must[must_cnt++] = {a , b};
sumM += a;
cntM++;
if(b < minB_M)
{
minB_M = b;
}
}
else
{
opt[opt_cnt++] = {a, b};
}
}
if(must_cnt == 0)
{
return true;
}
//贪心
sort(opt , opt + opt_cnt , [](auto &p1 , auto &p2)
{
return p1.second > p2.second;
});
int a_cnt = 0;
for(int i = 0;i < opt_cnt;i++)
{
all_a[a_cnt++] = opt[i].first;
}
sort(all_a , all_a + a_cnt);
m = unique(all_a , all_a + a_cnt) - all_a;
for(int i = 1;i <= m;i++)
{
bit_cnt[i] = 0;
bit_sum[i] = 0;
}
int b_cnt = 0;
for(int i = 0;i < must_cnt;i++)
{
all_b[b_cnt++] = must[i].second;
}
for(int i = 0;i < opt_cnt;i++)
{
all_b[b_cnt++] = opt[i].second;
}
sort(all_b , all_b + b_cnt);
b_cnt = unique(all_b , all_b + b_cnt) - all_b;
reverse(all_b, all_b + b_cnt);
int idx = 0;
for(int i = 0;i < b_cnt;i++)
{
ll minB = all_b[i];
if (minB > minB_M) continue;
while(idx < opt_cnt && opt[idx].second >= minB)
{
ll a = opt[idx].first;
int pos = lower_bound(all_a , all_a + m , a) - all_a + 1;
update(pos , a);
idx++;
}
int pos = upper_bound(all_a , all_a + m , minB) - all_a;
query(pos);
ll total_cnt = cntM + q_cnt;
ll total_sum = sumM + q_sum;
if(total_sum <= minB * total_cnt)
{
return true;
}
}
return false;
}
int main()
{
int T;
scanf("%d" , &T);
while(T--)
{
printf(solve() ? "YES\n" : "NO\n");
}
return 0;
}
```