Steven_MengのBlog

传送门

考虑尺取法求出所有满足条件的$i,j$,使$\sum ^j _{k=i}F_k>=M$,$O(n)$即可求出。

再考虑如何求$\max(S_i,S_{i+1},…S_{j-1},S_j)$

用线段树预处理即可

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
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define MAXN 100005
using namespace std;
ll S[MAXN],F[MAXN];
inline void lread(ll &x){
ll f=1ll;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1ll;
ch=getchar();
}
x=0;
while (ch<='9'&&ch>='0'){
x=(x<<3ll)+(x<<1ll)+(ll)(ch-'0');
ch=getchar();
}
x*=f;
}
struct SegmentTree{
struct node{
int l,r;
ll val;
}tree[MAXN<<2];
inline void pushup(int i){
tree[i].val=max(tree[i<<1].val,tree[i<<1|1].val);
}
void build(int l,int r,int i){
tree[i].l=l;
tree[i].r=r;
if (l==r){
tree[i].val=S[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
pushup(i);
}
ll query(int L,int R,int i){
int l=tree[i].l,r=tree[i].r;
if (L<=l&&r<=R){
return tree[i].val;
}
int mid=(l+r)>>1;
ll ans=-0x7fffffff;
if (L<=mid){
ans=max(ans,query(L,R,i<<1));
}
if (mid<R){
ans=max(ans,query(L,R,i<<1|1));
}
return ans;
}
}Seg;
int main(){
// freopen("hayfeast.in","r",stdin);
// freopen("hayfeast.out","w",stdout);
int n;
ll m;
scanf("%d%lld",&n,&m);
for (register int i=1;i<=n;++i){
lread(F[i]),lread(S[i]);
}
Seg.build(1,n,1);
int l=1,r=1;
ll sum=F[1],ans=0x7fffffff;
while (l<=n&&r<=n){
while (r<=n&&sum<m){
sum+=F[++r];
}
while (r<=n){
sum+=F[++r];
ll val=Seg.query(l,r,1);
if (val>=ans){break;}
else{ans=val;}
}
while (l<=r&&sum>=m){
sum-=F[l++];
}
}
printf("%lld\n",ans);
}

 评论