SP1108题解——二分和前缀和的应用-创新互联
第一次写题解，求赞求关注qwq
原题地址~
为了更好的理解题意我们可以看一下这个模拟：
假设一开始有 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://pwwzsj.com/article/dgshpi.html
