【LuoguP4085】【USACO17DEC】Haybale Feast
题目链接: https://www.luogu.org/problemnew/show/P4085
引言
好像教练说要考线段树和树状数组, 然后看到了这个题
这道题可以练习各种数据结构的基础操作…
我就浪费了大把时间用各种算法来A这道题
分析
先看这个 $ \sum_{k=i}^{j} F_k \geqslant M $
这个一眼看上去就是前缀和了.静态的话直接普通的前缀和$ O(n) $ 预处理, $ O(1) $ 查询就行了,应该是时间复杂度最低的了.
至于这个 $ max(S_i,S_{i+1},…,S_{j-1},S_j) $
维护方法就比较多了,可以用线段树,分块,ST表,我没有写树状数组,因为太麻烦了.
然后我就浪费了好多时间来用不同的算法A这道题…
这道题还有一个性质, 关于找i和j, 不需要 $ O(n^2) $ 的复杂度来枚举区间, 我给出下面这个式子
$$ max(s_i, s_{i + 1}, s_{i + 2}) <= max(s_i, s_{i + 1}, s_{i + 2}, s_{i + 3}) $$
这个式子根本不用推, 一眼看上去肯定就成立了
那么根据这个性质, 我们枚举i的值, 只需要找到一个对应的j就行了,这个j一定是满足条件且最小的那个了
满足条件只需要
$$ Sumf_j - sumf_i >= m $$
注: Sumf代表f数组的前缀和
那么我们可以用 $ O(logn) $ 的复杂度二分查询这个j了
我们其实不需要自己写二分查找,根据上面的不等式,移一下项,就变成了
$$ Sumf_j >= m + sumf_i $$
然后使用STL自带的lower_bound函数就可以了
维护区间最大值我建议写ST表, 毕竟静态查询时间复杂度 $ O(1) $, 你也可以写其他的, 我竟然写了三种数据结构.
代码
这个代码是线段树 + 前缀和, 评测详情 418ms / 6MB
ST_Table为ST表的代码, 评测详情 328ms / 9.53MB
Sqrt为分块,实在没找到英文名, 评测详情 1049ms / 7.65MB
m 和 前缀和要开long long, 其他的可以用int, 懒得话就全部 long long 吧
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
int n, f[100001], s[100001];
ll m;
inline int maxi(int a, int b) {
return a > b ? a : b;
}
inline int mini(int a, int b) {
return a < b ? a : b;
}
namespace PrefixSum {
ll sumf[100001];
void init() {
for(int i= 1; i <= n; i++) sumf[i]= sumf[i - 1] + f[i];
return;
}
}
namespace ST_Table {
int maxs[100001][18], _log2[100001];
void init() {
for(int i= 1; i <= n; i++) maxs[i][0]= s[i], _log2[i]= _log2[i - 1] + (i >= (1 << (_log2[i - 1] + 1)));
for(int j= 1; j < 18; j++)
for(int i= 1; i + (1 << j) <= n; i++) maxs[i][j]= maxi(maxs[i][j - 1], maxs[i + (1 << (j - 1))][j - 1]);
return;
}
int query(int l, int r) {
int __log2= _log2[r - l + 1];
return maxi(maxs[l][__log2], maxs[r - (1 << __log2) + 1][__log2]);
}
}
namespace Sqrt {
int blocks, maxs[100001], block[100001], bl[100001], br[100001];
void init() {
blocks= sqrt(n);
int cnt= n / blocks + (n % blocks & 1);
for(int i= 1; i <= n; i++) block[i]= (i - 1) / blocks + 1;
for(int i= 1; i <= cnt; i++) bl[i]= (i - 1) * blocks + 1, br[i]= i * blocks;
br[cnt]= mini(n, br[cnt]);
for(int i= 1; i <= cnt; i++)
for(int j= bl[i]; j <= br[i]; j++) maxs[i]= maxi(maxs[i], s[j]);
return;
}
int query(int l, int r) {
int x= block[l], y= block[r], ans= 0;
for(int i= x + 1; i < y; i++) ans= maxi(ans, maxs[i]);
for(int i= l; i <= br[x]; i++) ans= maxi(ans, s[i]);
for(int i= bl[y]; i <= r; i++) ans= maxi(ans, s[i]);
return ans;
}
}
namespace SegmentTree {
int maxs[100001 << 2];
void build(int nown, int l, int r) {
if(l == r) {
maxs[nown]= s[l];
return;
}
int mid= (l + r) >> 1;
build(nown << 1, l, mid);
build(nown << 1 | 1, mid + 1, r);
maxs[nown]= maxi(maxs[nown << 1], maxs[nown << 1 | 1]);
return;
}
int query(int nown, int l, int r, int ml, int mr) {
if(ml <= l && r <= mr) return maxs[nown];
int ans= 0, mid= (l + r) >> 1;
if(mid >= ml) ans= maxi(ans, query(nown << 1, l, mid, ml, mr));
if(mid < mr) ans= maxi(ans, query(nown << 1 | 1, mid + 1, r, ml, mr));
return ans;
}
inline void init() {
build(1, 1, n);
return;
}
inline int query(int l, int r) {
return query(1, 1, n, l, r);
}
}
int ans= 0x7f7f7f7f;
int main() {
scanf("%d%lld", &n, &m);
for(int i= 1; i <= n; i++) scanf("%d%d", f + i, s + i);
PrefixSum::init(), SegmentTree::init();
for(int i= 1; i <= n; i++) {
ll r= lower_bound(PrefixSum::sumf + i, PrefixSum::sumf + n + 1, m + PrefixSum::sumf[i - 1]) - PrefixSum::sumf;
if(r != n + 1) ans= mini(ans, SegmentTree::query(i, r));
}
printf("%d\n", ans);
return 0;
}
|
