正题
题目链接:https://ac.nowcoder.com/acm/contest/1101/A
题目大意
n
n
n天第
i
i
i天需要
a
i
a_i
ai台机器，每台机器可以工作
m
m
m天。
q
q
q次修改，每次修改一个
a
i
a_i
ai，求每次修改后至少需要雇佣多少台机器。
解题思路
很容易想到答案就是
m
a
x
{
a
i
,
⌈
s
u
m
m
⌉
}
max\{a_i,\lceil \frac{sum}{m}\rceil\}
max{ai,⌈msum⌉}
线段树维护即可。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std
;
const ll N
=4e5+10;
struct tree_node
{
ll l
,r
,w
;
};
ll n
,m
,q
,a
[N
],ans
;
struct node
{
tree_node t
[N
*4];
void Build(ll x
,ll l
,ll r
)
{
t
[x
].l
=l
;t
[x
].r
=r
;
if(l
==r
){
t
[x
].w
=a
[l
];
return;
}
ll mid
=(l
+r
)/2;
Build(x
*2,l
,mid
);
Build(x
*2+1,mid
+1,r
);
t
[x
].w
=max(t
[x
*2].w
,t
[x
*2+1].w
);
}
void Change(ll x
,ll pos
,ll num
){
if(t
[x
].l
==t
[x
].r
){
t
[x
].w
=num
;
return;
}
ll mid
=(t
[x
].l
+t
[x
].r
)/2;
if(pos
<=mid
) Change(x
*2,pos
,num
);
else Change(x
*2+1,pos
,num
);
t
[x
].w
=max(t
[x
*2].w
,t
[x
*2+1].w
);
}
}Tree
;
int main()
{
scanf("%lld%lld%lld",&n
,&m
,&q
);
for(ll i
=1;i
<=n
;i
++)
scanf("%lld",&a
[i
]),ans
+=a
[i
];
Tree
.Build(1,1,n
);
printf("%lld\n",max(Tree
.t
[1].w
,ans
/m
+((ans
%m
)?1ll:0ll)));
while(q
--){
ll x
,num
;
scanf("%lld%lld",&x
,&num
);
ans
+=num
-a
[x
];a
[x
]=num
;
Tree
.Change(1,x
,num
);
printf("%lld\n",max(Tree
.t
[1].w
,ans
/m
+((ans
%m
)?1ll:0ll)));
}
}
