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