大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
第一次写题解,求赞求关注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元起,快前往官网查看详情吧