自动搬运

查看原文

来自洛谷，原作者为

	focus_aurora 「既然选择了远方，就要风雨兼程。」|| AFO

搬运于2025-08-24 23:03:58，当前版本为作者最后更新于2024-09-17 21:47:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

分类讨论的数学题。

我们选择当前位置是一的情况进行讨论。

我们发现一个性质，下一轮前 $n$ 个转转楼梯的状态是上一轮第二个到第 $n+1$ 的状态，且若干次后，转转楼梯一定会全部变成零。

所以，分如下情况讨论。

当前位置的左边是一且右边是零的时候，此时只需要转动一次。总共转动 $i$ 次。

当前位置左右两边都是零的时候，此时需要转动两次。总共需要转动 $2\times i-1$ 次。

当前位置左边为零右边为一的时候，此时需要转动 $i-1$ 次。

然而我们只执行了 $k$ 轮。

所以所有的的答案记录都要让 $k$ 和 $i$ 取最小值进行操作。

最后，别忘赋初值。

代码

#include<bits/stdc++.h>
#define int long long//一定开long long！！！！！ 
using namespace std;
int a[2000005];
signed main(){
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}//输入 
	int ans=0;//答案记录变量 
	a[0]=1;//赋初值 
	for(int i=1;i<=n;i++){
		if(a[i]){
			if(a[i-1]&&!a[i+1]){//第一种情况 
				ans+=min(m,i);//和轮数取最小值 
			}
			if(!a[i-1]&&!a[i+1]){//第二种情况 
				int s=min(m,i);
				if(s==i){
					ans+=2*(s-1)+1;
				}
				else{
					ans+=2*s;
				}
			}
			if(!a[i-1]&&a[i+1]){//第三种情况 
				int s=min(m,i);
				if(s==i){
					ans+=s-1;
				}
				else{
					ans+=s;
				}
			}
		}
	}
	cout<<ans+m*n;//输出结果 
	return 0;
}