自动搬运

查看原文

来自洛谷，原作者为

	Hrz_OIer 一个超级蒟蒻

搬运于2025-08-24 22:32:17，当前版本为作者最后更新于2024-04-17 12:16:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P5186 和这道题怎么一模一样

思路

先考虑第一问

显然这是个“滑动窗口”的模型。

但是把每个滑动窗口刷的面积加起来并不是答案，因为一个位置可能会多次刷。

考虑删去重复部分，当上一个滑窗高度为 $last$，这个为 $now$ 时，容易发现重合的部分为：

$$\min \{{ last , now \}} \times (x − 1)$$

据此，就容易统计了。

code:

//初始 sum 为木板高度和
	int lstans=0;
	for(int i=1;i<=n;++i){
		while(head<=tail&&a[q[tail]]>a[i])tail--;
		while(head<=tail&&q[head]<=i-x)head++;
		q[++tail]=i;
		if(i>=x)
			mx[i-x+1]=a[q[head]]，//记录区间 [i-x+1,i] 的最小值，第二问用
			sum-=1ll*x*a[q[head]],
			sum+=1ll*min(a[q[head]],lstans)*(x-1),
			lstans=a[q[head]];}

考虑第二问

我们记第一问求得区间 $[i, i + x − 1]$ 的最小值为 $mx_i$ 。 则位置 $i$ 被刷的高度 $color_i$ 为：

$$color_i = \max \{{mx_i−x+1, mx_i−x+2, · · · , mx_i\}} $$

这又是个单调队列的式子，可以单调队列优化。

最后，我们知道了每个位置要刷的高度，要求刷的次数。则用贪心可求出：

• 若 $color_i \ne color_i−1$，则肯定要分开来刷。

• 若有 k 个刷的高度相同的连续位置，要刷 $\big\lceil \frac{k}{x} \big\rceil$ 次。

这样统计就行了。

code：

	for(int i=1;i<=n;++i){
		while(head<=tail&&mx[q[tail]]<mx[i])tail--;
		while(head<=tail&&q[head]<=i-x)head++;
		q[++tail]=i;
		brush[i]=mx[q[head]];}//记录刷的高度 
	int beg=-10000000,cnt=0;
	for(int i=1;i<=n;++i)
		//判断高度是否等于上一个，或者是太长刷不到了 
		if(brush[i]!=brush[i-1]||i>=beg+x)cnt++,beg=i;

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
#define int long long
int mx[N],q[N<<1],a[N],x,n,brush[N],head,tail,sum;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>x;
	for(int i=1;i<=n;++i)cin>>a[i],sum+=a[i];
	int lstans=0;
	for(int i=1;i<=n;++i){
		while(head<=tail&&a[q[tail]]>a[i])tail--;
		while(head<=tail&&q[head]<=i-x)head++;
		q[++tail]=i;
		if(i>=x)
			mx[i-x+1]=a[q[head]],
			sum-=1ll*x*a[q[head]],
			sum+=1ll*min(a[q[head]],lstans)*(x-1),
			lstans=a[q[head]];}
	for(int i=1;i<=n;++i){
		while(head<=tail&&mx[q[tail]]<mx[i])tail--;
		while(head<=tail&&q[head]<=i-x)head++;
		q[++tail]=i;
		brush[i]=mx[q[head]];}
	int beg=-10000000,cnt=0;
	for(int i=1;i<=n;++i)if(brush[i]!=brush[i-1]||i>=beg+x)cnt++,beg=i;
	cout<<sum<<"\n"<<cnt;
	return 0;}

制作不易，点个赞吧！（ QAQ ）