题意:
给定两个栈,每次操作可以花费一个代价将栈顶的元素放到另一个栈的栈顶,如果当前序列的最大值是栈顶,可以0花费将这个最大值弹出。问最少操作多少次。
思路:
由于这样操作的序列是确定的,那么就没有贪心的成分所在了,就是想着怎么模拟了,一开始想用平衡树,由于某个数的上面的一堆数放到隔壁堆中,实现翻转,对于隔壁堆下面的所有元素,都加上size,但是没必要,看了标程,其实可以实现这样的操作。
将所有数按照值大小,从大到小排序,维护每一个id,然后每次都维护当前板所在的位置,最后实现一个线段树单点修改区间查询就行了,由于板子pos这个位置既可以定义为在某个点后面,也可以选择在某个点前面,代码里我选择的是在某个点后面,维护起来可以能不一样。本题坑点在于输入很阴间=-=,要小心,复杂度O(nlogn).
代码: #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 400010;
int a[N];
struct p{
int x;
int pos;
bool operator<(const p&w)const
{
return x>w.x;
}
}q[N];
struct node{
int l;
int r;
int sum;
}tr[N<<2];
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void mdf(int u,int x)
{
if(tr[u].l==tr[u].r &&tr[u].l==x)
{
tr[u].sum=0;
return ;
}
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid)mdf(u<<1,x);
elsemdf(u<<1|1,x);
pushup(u);
}
void build(int u,int l,int r)
{
tr[u]={l,r};
if(l==r)
{
tr[u].sum=1;
return ;
}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
int query(int u,int l,int r)
{
if(l>r)
return 0;
if(tr[u].l>=l && tr[u].r<=r)
return tr[u].sum;
int mid=tr[u].l+tr[u].r>>1;
int res=0;
if(l<=mid)res+=query(u<<1,l,r);
if(r>mid)res+=query(u<<1|1,l,r);
return res;
}
int main()
{
int n1,n2;
cin>>n1>>n2;
int n=n1+n2;
for(int i=n1;i>=1;i--)
{
cin>>a[i];
q[i]={a[i],i};
}
for(int i=n1+1;i<=n1+n2;i++)
{
cin>>a[i];
q[i]={a[i],i};
}
long long res=0;
sort(q+1,q+1+n);
build(1,1,n);
int pos=n1;
for(int i=1;i<=n;i++)
{
int x=q[i].x;
int nowpos=q[i].pos;
if(pos>nowpos)
{
res+=query(1,nowpos+1,pos);
mdf(1,nowpos);
pos=nowpos-1;
}
else if(pos<nowpos)
{
res+=query(1,pos+1,nowpos-1);
mdf(1,nowpos);
pos=nowpos;
}
else
{
mdf(1,nowpos);
}
//cout<<nowpos<<" res="<<res<<" x="<<x<<" "<<" pos="<<pos<<endl;
}
cout<<res<<endl;
return 0;
}
|