- 陶陶的背包
- 2019-05-15 14:00:44 @
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,len[100010],cnt,maxn;
struct node{
int lson,rson,sum,weight;
}tree[2000010];
struct gold{
int w,v;
}a[100010],b[100010];
bool cmp(gold x,gold y){
return ((double)(x.v)/x.w)>((double)(y.v)/y.w);
}
int build(int l,int r){
int x=++cnt,mid=(l+r)/2;
if(l<r){
tree[x].lson=build(l,mid);
tree[x].rson=build(mid+1,r);
}
return x;
}
int upt(int x,int l,int r,int p,gold g){
int k=++cnt,mid=(l+r)/2;
tree[k].lson=tree[x].lson;
tree[k].rson=tree[x].rson;
tree[k].sum=tree[x].sum+g.v;
tree[k].weight=tree[x].weight+g.w;
if(l<r){
if(p<=mid) tree[k].lson=upt(tree[x].lson,l,mid,p,g);
else tree[k].rson=upt(tree[x].rson,mid+1,r,p,g);
}
return k;
}
double query(int u,int v,int l,int r,int ls,int rs){
int wi=tree[v].weight-tree[u].weight,vi=tree[v].sum-tree[u].sum,mid=(l+r)/2;
if(l>r||!maxn||!wi) return 0;
if(l==r){
if(maxn>=wi){
maxn-=wi;
return vi;
}
else return (double)vi*((double)maxn/wi);
}
if(l<=ls&&r>=rs&&maxn>=wi){
maxn-=wi;
printf("%d %d\n",wi,vi);
return vi;
}
return query(tree[u].lson,tree[v].lson,l,mid,ls,rs)+query(tree[u].rson,tree[v].rson,mid+1,r,ls,rs);
}
map<double,int> ma;
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i].v),b[i].v=a[i].v;
for(int i=1;i<=n;i++) scanf("%d",&a[i].w),b[i].w=a[i].w;
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++) ma.insert(make_pair((double)b[i].v/b[i].w,i));
len[0]=build(1,n);
for(int i=1;i<=n;i++){
map<double,int>::iterator x=ma.find((double)a[i].v/a[i].w);
len[i]=upt(len[i-1],1,n,x->second,b[x->second]);
// print(1,1,n);
// printf("\n");
}
for(int i=1;i<=m;i++){
scanf("%d %d %d",&l,&r,&maxn);
double ans=query(len[l-1],len[r],1,n,l,r);
ans+=1e-3;
if(i!=m) printf("%.2lf ",ans);
else printf("%.2lf",ans);
}
}
哪位大佬帮忙调一下
0 条评论
目前还没有评论...