[二分] UOJ49. [UR #3]铀仓库

容易想到,拿的是一个区间,且区间中每个物品的代价是到 \(s\) 距离的两倍。

如果已经固定一个区间,起点肯定取在物品数量中位数的位置。

二分答案,验证的话肯定是左端点推,右端点推的那种搞法...

对于一个区间,我们很难直接 \(O(1)\) 求中位数的位置,二分的话可能就两个 \(log\) 了。

所以干脆动 \(s\) ,端点跟着调整。注意细节就好了... \(O(n \log n)\)

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
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn=100005;
typedef long long LL;
using namespace std;
LL n,m,a[maxn],px[maxn],sz[maxn],sum[maxn],pre[maxn];
LL Calc(int mid,int l,int r){
LL tmp=0;
tmp+=pre[r]-pre[mid]-px[mid]*(sum[r]-sum[mid]);
tmp+=px[mid]*(sum[mid-1]-sum[l-1])-pre[mid-1]+pre[l-1];
tmp-=(a[r]-sz[r])*(px[r]-px[mid]);
tmp-=(a[l]-sz[l])*(px[mid]-px[l]);
return tmp<<1;
}
bool check(LL k){
memset(sz,0,sizeof(sz));
int L=1,R=0; LL tmp=k;
while(tmp){
R++; sz[R]=min(a[R],tmp); tmp-=sz[R];
if(Calc(1,L,R)<=m) return true;
for(int i=2;i<=n;i++){
while(px[i]-px[L]>px[R]-px[i]){
if(sz[R]==a[R]){
if(R<n){ R++; continue; }
break;
}
tmp=min(a[R]-sz[R],sz[L]);
sz[R]+=tmp; sz[L]-=tmp;
if(!sz[L]) L++;
}
if(Calc(i,L,R)<=m) return true;
}
return false;
}
LL ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&px[i]);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
pre[i]=pre[i-1]+px[i]*a[i];
}
LL L=0,R=sum[n];
while(L<=R){
int mid=(L+R)>>1;
if(check(mid)) L=mid+1, ans=mid; else R=mid-1;
}
printf("%lld\n",ans);
return 0;
}