洛谷 1 月月赛 III
B. 多边形
大致题意：给定一个长度为 的数组 ，对于 ，判断能否恰好从 中选取 个数拼成一个面积严格大于 的多边形。
思路：容易观察到一组数能组成一个 边形的充要条件是任意一条边都小于剩余 条边的和，亦即满足最小的 个数的和比最大的数大就可以。当 作为最长边时，很容易想到其余 条边要取比 小的最大的 个数，故 需要排序+前缀和维护区间。且若
成立，则对于任意的
一定成立，此时将 区间标记为 true。
由于数组已排序，区间和具有单调性，故 可通过二分查找求得，区间标记可通过差分单点维护首尾的状态，最后再将 遍历一遍复原标记状态即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <bits/stdc++.h>
#define int long long
using namespace std;
int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
signed main() {
int n = read();
vector<int> a(n);
for (int i = 0; i < n; i++) {
a[i] = read();
}
sort(a.begin(), a.end());
vector<int> pre_sum(n + 1);
for (int i = 0; i < n; i++) {
pre_sum[i + 1] = pre_sum[i] + a[i];
}
vector<int> diff(n + 2, 0);
for (int i = 2; i < n; i++) {
int l = 3, r = i + 1, k_min = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int tot = pre_sum[i + 1] - pre_sum[i - mid + 1];
if (tot > 2 * a[i]) {
k_min = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (k_min != -1) {
diff[k_min]++;
diff[i + 2]--;
}
}
int cnt = 0;
for (int k = 3; k <= n; k++) {
cnt += diff[k];
if (cnt > 0) {
cout << k << " ";
}
}
cout << endl;
return 0;
}
|
整体复杂度 。
如果我们不使用二分查找，对于每个 ，都判断是否存在一个 ，使得
成立，这样将十分简便，但这样逻辑似乎是 ？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bool check(int k, int n) {
for (int i = k; i <= n; i++) {
if (s[i - 1] - s[i - k] > a[i]) {
return 1;
}
}
return 0;
}
signed main() {
for (int k = 3; k <= n; k++) {
if (check(k, n)) {
cout << k << endl;
}
}
}
|
事实并非如此。虽然其表面上看是两重循环，但实际上会有很大一部分被剪枝掉，也就是说当 很大的时候，check 函数一般来说很快就会返回 ，内层循环不会到 的级别。
证明很容易，我们考虑 check 函数能执行满的最坏情况，令 ，，在这种情况下，如果
仍成立，则 的值至少要为
可以看到 其实就是一个二阶的斐波那契数列，呈指数级增长，证明显然。
由于题中的 最大值为 ，故内层循环的最大量级为 是一个常数，整体复杂度 ，并不会超时。
相当于求 阶斐波那契数列特征根中最大值。对于 阶斐波那契数列，其特征方程为
当 时，右侧为等比数列求和
整理，得
即
由于 ，故
事实上，其收敛到 ，且为指数级快速趋近，具体证明读者可自行探索。
C. 传送
（未完待续……）