题意
有 $n$ 个生物，第 $i$ 个生物有大小 $A_i$ 和颜色 $i$。
第 $i$ 个生物可以吞噬第 $j$ 个元素当：
$$A_j \leq 2 \cdot A_i$$这些生不停的吞噬这其它生物，最终成为一个生物。求该生物可能的颜色的数量。
$2 \leq n \leq 10^5, 1 \leq A_i \leq 10^9$
题解
考虑第 $i$ 个生物有没有可能成为最终的那个生物：
第 $i$ 个生物必然是从大小最小的生物开始吞噬，如果最后全部吞噬了，那么这个生物就是答案之一。
这样得到了一个 $\mathcal O\left(n^2\right)$ 的算法。
考虑如何优化：
- 把数组排序，二分从哪个点开始可以。
- 考虑到如果生物 $i$ 不能成为最后一个生物，那么一定是 $i$ 的前缀和的两倍小于第 $i + 1$ 个点的大小。所以，把数组排序，从右往左 找到第一个 $i$ 的前缀和的两倍小于第 $i + 1$ 个点的大小的点。那么这个点，以及更靠前的点不然不能成为最后一个生物。
因为要排序，复杂度是 $\mathcal O\left(n \log n\right)$。
代码
// By rbtree (https://rbtr.ee)
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define ra _Read()
using tp = long long;
tp _Read();
using namespace std;
constexpr bool __MTCS__ = 0;
constexpr tp Hat_N = 1e5 + 3;
namespace __SOL__ {
signed main() {
tp n = ra, cnt = 0;
array<tp, Hat_N> a, s;
for (tp i = 1; i <= n; ++i) {
a[i] = ra;
}
stable_sort(a.begin() + 1, a.begin() + n + 1);
for (tp i = 1; i <= n; ++i) {
s[i] = s[i - 1] + a[i];
}
for (tp i = n; i; --i) {
if (s[i] * 2 < a[i + 1]) {
break;
}
++cnt;
}
cout << cnt << '\n';
return 0;
}
} // namespace __SOL__
signed main() {
tp __MTCS__ = ::__MTCS__ ? ra : 1;
while (__MTCS__--) {
__SOL__::main();
}
return EXIT_SUCCESS;
}
tp _Read() {
bool __neg(0);
char __c(getchar());
tp __val(0);
for (; __c < 48 || __c > 57; __c = getchar()) {
__neg = __c == 45;
}
for (; __c > 47 && __c < 58; __c = getchar()) {
__val = __val * 10 + (__c & 15);
}
return __neg ? ~__val + 1 : __val;
}
/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/