专栏首页一Wa哇一天E. Permutation Separation

E. Permutation Separation

E. Permutation Separation

E. Permutation Separation time limit per test:2 seconds memory limit per test:256 megabytes inputstandard input outputstandard output

 You are given a permutation p1,p2,…,pn (an array where each integer from 1 to n appears exactly once). The weight of the i-th element of this permutation is ai.  At first, you separate your permutation into two non-empty sets — prefix and suffix. More formally, the first set contains elements p1,p2,…,pk, the second — pk+1,pk+2,…,pn, where 1≤k<n.  After that, you may move elements between sets. The operation you are allowed to do is to choose some element of the first set and move it to the second set, or vice versa (move from the second set to the first). You have to pay ai dollars to move the element pi.  Your goal is to make it so that each element of the first set is less than each element of the second set. Note that if one of the sets is empty, this condition is met.  For example, if p=[3,1,2] and a=[7,1,4], then the optimal strategy is: separate p into two parts [3,1] and [2] and then move the 2-element into first set (it costs 4). And if p=[3,5,1,6,2,4], a=[9,1,9,9,1,9], then the optimal strategy is: separate p into two parts [3,5,1] and [6,2,4], and then move the 2-element into first set (it costs 1), and 5-element into second set (it also costs 1). Calculate the minimum number of dollars you have to spend.

Input The first line contains one integer n (2≤n≤2⋅10^5^) — the length of permutation. The second line contains n integers p1,p2,…,pn (1≤pi≤n). It’s guaranteed that this sequence contains each element from 1 to n exactly once. The third line contains n integers a1,a2,…,an (1≤ai≤10^9^). Output Print one integer — the minimum number of dollars you have to spend.

Examples input

3
3 1 2
7 1 4

output

4

input

4
2 4 1 3
5 9 8 3

output

3

input

6
3 5 1 6 2 4
9 1 9 9 1 9

output

2

题目大意

给你一个数 n ,然后有n个数,给个数对应一个权值ai,然后让你将这n个数分成两个空的几何,通过移动两个几何中的元素,使得最终的左侧几何的数全部小于右侧几何的数,有个特殊情况: 如果移动到最后一个几何为空,那么也成立。移动每一个元素时都要加上对应的权值,问你是如何移动使得花费最小。 比如说第一个样例 3 1 2 这三个数分别对应的权值是 7 1 4,我们可以选择将几何这个序列分成两部分,【3,1】,【2】,这样的话,将2移动到前那个几何中就可以花费为 4且代价最少。

解题思路

这题我们可以考虑把前K个数里面的比K大的数都移动到K后面,K后面比K小的数都移动到K前面,但是如果直接这样写是N^2^的复杂度,这时候我们就要想想可以用什么来优化下了,我们可以模拟先来一遍 就第一个样例吧,刚开始是 3 5 1 6 2 4,对应的权值为9 1 9 9 1 9;假设这时候我们考虑把前k个数全部移动到后面的花费 分别是 9 10 19 28 29 9(对于最后一个数,我们可以考虑,把他向前一个移动) 这是我们发现其实对于前K个数而言,只要其小于等于K,就不用移动,对于K后面的数如果大于K就不用移动,这时候我们该如何优化呢,如果数字 i 的位置在 i 之前,那么 i 位置后面的前缀和要减去 i 的权值,但是要向前去移动,再算前缀和的时候,它前面的数值没有加上他,所以从数字 i 的 位置之前的前缀和都要加上 i 的权值,从 i 的位置开始以后的前缀和都要减去 i 的权值;这样我们就可以线性的跑一遍数列并且以 log 级别的进行计算。 例如: 的后 【3 5 1 6 2 4】 k=1时: 1前面的数字都要加上1的权值,后面的减去1的权值。 k=2时: 2前面的数字都要加上2的权值,后面的减去2的权值。这时候可以发现,2这个位置的前缀和刚好只有3 5 6,这几个数值的权值和, k=3时: 3前面的数字都要加上3的权值,后面的减去3的权值,这时候3这个位置的前缀和变成了 1,2这两个数值的前缀和,并且1这个位置的前缀和变成了2 和5 的权值和了。 后面的也类似就不一一举例了。 线段树本菜鸡也是刚刚学,还请大佬们多多指导。。。

代码

#include<bits/stdc++.h>
using namespace std;
const int mx=200015;
#define ll long long
ll sum[mx];
int a[mx],pos[mx],b[mx];
struct node{
    ll mi,lazy;
} tree[mx<<2];
int n;

inline void build(int x,int l,int r)
{
    if(l==r) {
        tree[x].mi=sum[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    tree[x].mi=min(tree[x<<1].mi,tree[x<<1|1].mi);
    return ;
}

inline void push_down(int x,int l,int r)
{
    tree[x<<1].lazy+=tree[x].lazy;
    tree[x<<1].mi+=tree[x].lazy;
    tree[x<<1|1].lazy+=tree[x].lazy;
    tree[x<<1|1].mi+=tree[x].lazy;
    tree[x].lazy=0;
}

inline void update(int x,int l,int r,int ql,int qr,ll k)
{
    if(r<ql||l>qr) return;
    if(l>=ql&&r<=qr){
        tree[x].lazy+=k;
        tree[x].mi+=k;
        return ;
    }
    push_down(x,l,r);
    int mid=(l+r)>>1;
    update(x<<1,l,mid,ql,qr,k);
    update(x<<1|1,mid+1,r,ql,qr,k);
    tree[x].mi=min(tree[x<<1].mi,tree[x<<1|1].mi);
    return ;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        pos[a[i]]=i;//记录a[i]的位置
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        sum[i]=sum[i-1]+b[i];//计算前缀和
    }
    build(1,1,n-1);//建树建到 n-1;
    ll ans=tree[1].mi;//考虑将最后一个数移动到前面花费最小;
    for(int i=1;i<=n;i++)
    {
        update(1,1,n-1,1,pos[i]-1,b[pos[i]]);//这个位置之前的数都要加上i的权值
        update(1,1,n-1,pos[i],n-1,-b[pos[i]]);//这个位置开始以后的数值都要减去i的权值
        ans=min(ans,tree[1].mi);//每次更新最小的情况
    }
    cout<<ans<<'\n';
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • F2. Animal Observation (hard version)

    time limit per test:3 seconds memory limit per test:512 megabytes inputstandard ...

    某些人
  • 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

    Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

    某些人
  • D. Minimax Problem

    time limit per test:5 seconds memory limit per test:512 megabytes inputstandard ...

    某些人
  • POJ-2181 Jumping Cows(贪心)

    Jumping Cows Time Limit: 1000MS Memory Limit: 65536K Total Submissions:...

    ShenduCC
  • visualize your CDS view via Analysis Path Framework (APF)

    Create a new configuration which acts as a container for sub settings such as Fi...

    Jerry Wang
  • WPF框架的内存泄漏BUG

        用户在使用GIX4某模块的过程中,内存只见加不见减。我们怀疑出现了内存泄漏,所以我花了相当一段时间来进行此问题的排查。     我使用Red Gate公...

    用户1172223
  • SAP UI5应用的调试标志位的本地存储逻辑 - local storage使用的一个例子

    We know that once we enable debug mode via “Ctrl+Alt+Shift+P”, this setting will...

    Jerry Wang
  • 多语种机器翻译: 缩小共享和特定语言编码解码器之间的差距(CS CL)

    最先进的多语种机器翻译依赖于通用的编码解码器,这需要重新训练整个系统来添加新的语言。 在本文中,我们提出了一种基于特定语言编码解码器的替代方法,从而可以更容易地...

    用户7095611
  • 【2019年8月版本】OCP 071认证考试最新版本的考试原题-第2题

    Which three are true about the CREATE TABLE command?

    用户5892232
  • APF model和Fiori launchpad tile的同步问题

    If I create a new representation in APF modeler:

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券