预处理把左集划分为大小为1~i-1时,把全部元素都移动到右集的代价,记作sum[i]。

然后枚举终态时左集的大小,更新把元素i 留在/移动到 左集的代价。

树状数组/线段树处理区间修改/区间查询

 #define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+;
struct Tree{
ll minn,lazy;
}tree[N<<];
ll sum[N];//前缀和
inline void build(int root,int l,int r){
if(l==r){
tree[root].minn=sum[l];//1~l的a[i]之和
tree[root].lazy=;
return;
}
int mid=(l+r)>>;
build((root<<),l,mid);
build((root<<|),mid+,r);
tree[root].minn=min(tree[(root<<)].minn,tree[(root<<|)].minn);//up
return;
}
inline void pushdown(int root){
if(!tree[root].lazy)
return;
tree[(root<<)].minn+=tree[root].lazy;
tree[(root<<|)].minn+=tree[root].lazy;
tree[(root<<)].lazy+=tree[root].lazy;
tree[(root<<|)].lazy+=tree[root].lazy;
tree[root].lazy=;
return;
}
inline void change(int root,int l,int r,int x,int y,int val){
if(r<x||l>y)
return;
if(x<=l&&r<=y){
tree[root].minn+=val;
tree[root].lazy+=val;
return;
}
int mid=(l+r)>>;
pushdown(root);
change((root<<),l,mid,x,y,val);
change((root<<|),mid+,r,x,y,val);
tree[root].minn=min(tree[(root<<)].minn,tree[(root<<|)].minn);//up
return;
}
int n,p[N],a[N],pos[N];
ll ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(int i=;i<=n;++i){
cin>>p[i];
pos[p[i]]=i;//数字p[i]出现的位置为i
}
for(int i=;i<=n;++i){
cin>>a[i];
sum[i]=sum[i-]+a[i];//sum[i]为左集合大小为i,把左集合所有元素都移动到右集合的花费
}
build(,,n-);
ans=min(a[],a[n]);//a[1]为左集为空,a[n]为右集为空
for(int i=;i<n;++i){//枚举左集大小,定下大小后,集合内元素也被定为1~i
change(,,n-,,pos[i]-,a[pos[i]]);//找到元素i出现的位置,在它出现位置左边的sum[i]分别加上把元素i从右集合移动到左集合的代价(原本的sum[1~i-1]为把原本处于位置1~i-1的元素都移动到右边,此时加上元素1~i从右移动到左的代价)
change(,,n-,pos[i],n,-a[pos[i]]);//在它出现位置及其右边的sum[i]分别减去把元素i从左集合移动到右集合的代价(元素i无需移动,可是移动的代价事先已经加到sum[i~n]里了)
ans=min(ans,tree[].minn);//如果左集大小为i的代价最小就更新最小值
}
cout<<ans;
return ;
}

最新文章

  1. Android开发学习之路-EventBus使用
  2. es6 class
  3. iOS开发——UI进阶篇(十三)UITabBarController简单使用,qq主流框架
  4. 爬虫:获取多次跳转后的页面url
  5. 在windows系统上安装VMware Workstation虚拟机,然后在虚拟机VMware Workstation上安装linux系统,在linux系统安装xshell的服务端,在windows系统上安装xshell。用windows系统上的xshell连接到linux
  6. chmod,chown和chgrp的区别
  7. hdu 4604 Deque(最长上升与下降子序列-能够重复)
  8. Listview右侧 IndexBar
  9. C#星夜拾遗之delegate示例
  10. 董事局主席董事长总裁首席执行官CEO总裁董事监事区别
  11. C++复数运算 重载
  12. django 之manytomany
  13. HDU 5956 The Elder (树上斜率DP)
  14. 如何优化mysql查询速度
  15. linux关于ftp查看不到文件列表的问题
  16. 【Sonarqube】windows下更改Temp文件夹的位置
  17. Web应用扩展系列(1):架构篇(转)
  18. ZIP排除指定目录进行压缩
  19. Manthan, Codefest 16 G. Yash And Trees dfs序+线段树+bitset
  20. go语言基础之开发工具

热门文章

  1. 树莓派操作案例1-使用python GPIO+TB6612驱动步进电机
  2. linux上部署springboot应用的脚本
  3. jdbc url的若干参数
  4. ModuleNotFoundError: No module named &#39;numpy.testing.nosetester&#39;
  5. 后端——框架——缓存框架——memcached——《Memcached教程》阅读笔记
  6. Lumen 实现接口 Captcha图片验证码功能
  7. SSM开发基于Java EE在线图书销售系统
  8. Itext相关知识
  9. django入门与实践(续)
  10. js面向对象的程序设计 --- 下篇 继承启蒙