第一次写题解，求赞求关注qwq
成都创新互联是一家专注网站建设、网络营销策划、小程序定制开发、电子商务建设、网络推广、移动互联开发、研究、服务为一体的技术型公司。公司成立10余年以来，已经为上1000+
柔性防护网各业的企业公司提供互联网服务。现在，服务的上1000+客户与我们一路同行，见证我们的成长；未来，我们一起分享成功的喜悦。
原题地址~
为了更好的理解题意我们可以看一下这个模拟：
假设一开始有
5
5
5 张牌，初始顺序分别是
1
,
2
,
3
,
4
,
5
1,2,3,4,5
1,2,3,4,5。
第
1
1
1 次把最顶层的
1
1
1 依次拿到下面，顺序变成
2
,
3
,
4
,
5
,
1
2,3,4,5,1
2,3,4,5,1；接着把最上面的
2
2
2 拿走，第一轮操作后的数列为
3
,
4
,
5
,
1
3,4,5,1
3,4,5,1。
第
2
2
2 次把最顶层的
3
,
4
3,4
3,4 依次拿到下面，顺序变成
5
,
1
,
3
,
4
5,1,3,4
5,1,3,4；接着把最上面的
5
,
1
5,1
5,1 拿走，第一轮操作后的数列为
3
,
4
3,4
3,4。
最后一次需要进行
3
3
3 次操作，可是只有
2
2
2 个数，怎么办呢？把
3
,
4
3,4
3,4 依次拿到下面三次，也就是
3
,
4
→
4
,
3
→
3
,
4
→
4
,
3
3,4 \rightarrow 4,3 \rightarrow 3,4 \rightarrow 4,3
3,4→4,3→3,4→4,3 。
最后的数列为
2
,
5
,
1
,
4
,
3.
2,5,1,4,3.
2,5,1,4,3.
而题目想让你求的是使最后的数列单调上升，即最后的数列为
1
,
2
,
3
,
4
,
5
1,2,3,4,5
1,2,3,4,5.
我们再用样例来测试一下，
n
=
5
n = 5
n=5，初始顺序为
3
,
1
,
4
,
5
,
2
3,1,4,5,2
3,1,4,5,2.
第
1
1
1 次把最顶层的
3
3
3 依次拿到下面，顺序变成
1
,
4
,
5
,
2
,
3
1,4,5,2,3
1,4,5,2,3；接着把最上面的
1
1
1 拿走，第一轮操作后的数列为
4
,
5
,
2
,
3
4,5,2,3
4,5,2,3。
第
2
2
2 次把最顶层的
4
,
5
4,5
4,5 依次拿到下面，顺序变成
2
,
3
,
4
,
5
2,3,4,5
2,3,4,5；接着把最上面的
2
,
3
2,3
2,3 拿走，第一轮操作后的数列为
4
,
5
4,5
4,5。
最后一次把
4
,
5
4,5
4,5 依次拿到下面，也就是
4
,
5
→
5
,
4
→
4
,
5
4,5 \rightarrow 5,4 \rightarrow 4,5
4,5→5,4→4,5 。
最后的数列刚好为
1
,
2
,
3
,
4
,
5
1,2,3,4,5
1,2,3,4,5，符合题意。XD
理解了题意，我们看数据范围：
n
≤
2
×
1
0
4
n \le 2 \times 10^4
n≤2×104 ，另一篇题解用
O
(
能
过
)
O(能过)
O(能过) 的暴力，很明显运用了区间求和的操作，这时候我们会想到 前缀和/树状数组/线段树。
因为我有强迫症刚学树状数组，所以我就自然要用求和复杂度为
O
(
log
n
)
\mathcal{O} (\operatorname{log}n)
O(logn) 的树状数组解决啦~
附赠树状数组板子：
// P.S:f为树状数组
int lowbit(int i){return i&-i;
}
int getsum(int n){int ans = 0;
while(n>0){ans+=f[n];
n-=lowbit(n);
}
return ans;
}
void change(int i,int d,int n){while(i<=n){f[i]+=d;
i+=lowbit(i);
}
}
通过题目得知最后的序列是单调上升的，还原时自然会想到复杂度为
O
(
log
n
)
\mathcal{O}(\operatorname{log} n)
O(logn) 的二分来处理前缀和。
int BinarySearch(int val,int n){int l = 1,r = n;
while(lint mid = (l+r)>>1;
if(getsum(mid)>=val) r = mid;
else l = mid+1;
}
return l;
}
所以这种做法总的时间复杂度是
O
(
n
l
o
g
2
n
)
\mathcal{O}(n \operatorname{log^2} n)
O(nlog2n)。
最后就是核心代码啦，注释都在代码里。
void work(int n){memset(f,0,sizeof f);//多测不清空，抱灵两行泪
int p = 0,c = n,pl,pr,step;//p是当前处理的元素（就是指针）
for(int i = 1;i<=n;i++){change(i,1,n);//将初始的1,2,3...n存入到树状数组中
}
for(int i = 1;i<=n;i++){step = (i+1)%c;//处理步数比元素多的情况
pl = getsum(p),pr = c-pl;//需要更改的范围
int nxt;
nxt = (step<=pr)?step+pl:step-pr;二分范围
if(nxt==0) nxt = c;
p = BinarySearch(nxt,n);
ans[p] = i;//填入答案
change(p,-1,n);//填完了~
c--;
}
for(int i = 1;i<=n;i++) cout<
代码就不提供了，主函数没有什么东西了qwq
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网站栏目：SP1108题解——二分和前缀和的应用-创新互联
文章起源：
http://cdkjz.cn/article/dgshpi.html
