本文共 2013 字，大约阅读时间需要 6 分钟。
第一眼感觉是个水题
过程确实也无脑，但是细节麻烦。。。
就是循环找最小值，删除，算步数而已
不过转移位置的计算我试了好几种方法，才写出一个对的。。
提交时一度抱着求求你让我过吧这种心态（
#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define ll long long#define pb push_back#define FOR(a) for(int i=1;i<=a;i++)const int inf=0x3f3f3f3f;const int maxn=1e5+9; const int mod=1e9+7;int arr[maxn];int now;struct NODE{ int minn;int minid;int cnt;}ST[maxn<<2];void pushup(int rt){ ST[rt].cnt=ST[rt<<1].cnt+ST[rt<<1|1].cnt; ST[rt].minn=min(ST[rt<<1].minn,ST[rt<<1|1].minn); if(ST[rt<<1].minn<=ST[rt<<1|1].minn)ST[rt].minid=ST[rt<<1].minid; else ST[rt].minid=ST[rt<<1|1].minid;}void build(int l,int r,int rt){ if(l==r){ST[rt].minn=arr[l];ST[rt].minid=l;ST[rt].cnt=1;return;} int m=l+r>>1;build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushup(rt);}void update(int a,int l,int r,int rt){ if(l==r){ST[rt].minn=inf;ST[rt].cnt=0;return;} int m=l+r>>1;if(a<=m)update(a,l,m,rt<<1);else update(a,m+1,r,rt<<1|1); pushup(rt);}int query(int a,int b,int l,int r,int rt){ if(a<=l&&b>=r)return ST[rt].cnt; int m=l+r>>1; int ret=0; if(a<=m)ret+=query(a,b,l,m,rt<<1); if(b>m)ret+=query(a,b,m+1,r,rt<<1|1); return ret;}int query2(int a,int b,int l,int r,int rt){ if(a<=l&&b>=r && ST[rt].minn==ST[1].minn)return ST[rt].minid; else if(a<=l && b>=r)return -1; int m=l+r>>1; int a1=-1,a2=-1; if(a<=m)a1=query2(a,b,l,m,rt<<1); if(b>m)a2=query2(a,b,m+1,r,rt<<1|1); if(a1==-1 && a2==-1)return -1; else if(a1!=-1)return a1; else return a2;}int main(){ int n;scanf("%d",&n); FOR(n)scanf("%d",&arr[i]); build(1,n,1); now=0;ll ans=0; for(int i=1;i<=n;i++){ //删n轮 //int nex=ST[1].minid; int nex=query2(now,n,1,n,1); //if(now==10)cout<<"www"< < now){ ans+=query(now,nex,1,n,1); now=nex; update(nex,1,n,1); }else{ ans+=query(now,n,1,n,1)+query(1,nex,1,n,1); now=nex; update(nex,1,n,1); } } printf("%lld\n",ans);}
转载于:https://www.cnblogs.com/Drenight/p/8611284.html