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