自动搬运

查看原文

来自洛谷，原作者为

	chen_kun 生命绚烂，别被黑暗压垮。

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

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

以下是正文

题解：P12663 [KOI 2023 Round 2] 湖边的蚁穴

思路简述

这题还是比较简单的。

用数组 $a$ 代表第 $i$ 个大房间有 $a_i$ 个小房间，用变量 $cnt$ 代表能住几只蚂蚁。

首先遍历整个 $a$ 数组。

因为有通道直接连接的两个房间不能同时住蚂蚁，而小房间与其他的大房间没有通道直接连接，因此有小房间就让它直接住满蚂蚁即可。即若房间 $a_i$ 不为 0，则 cnt+=a[i];。

那么如果当前的大房间没有小房间，则找出一整段连续的没有小房间的大房间，用变量 $t$ 记录它们的个数，直到找到一个有小房间的大房间再统一结算。因为相邻的两个大房间不能同时住蚂蚁，所以这一连串的 $t$ 的大房间仅有一般的房间可以住蚂蚁，如果 $t$ 为奇数则可以在 $t$ 的一半的基础上再多住一只，即 cnt=cnt+t/2+t%2;。

另外由于数组是环状的，所以如果数组首尾都是 0 的话有点难处理，所以我们可以把开头所有的 0 都丢到数组的末尾将它们强制首尾相接，就简单很多了。

代码呈现

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=255555;
int cnt,n,a[2*N],mmax,t,st,f=1;//由于要首尾相接所以数组的大小要开到2*N 
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]!=0&&!st) st=i;//st用于记录第一个非0的数的位置 
		if(!st) a[i+n]=a[i];//如果开头是0就丢到数组末尾 
	}
	if(!st){//如果全是0直接输出即可 
		cout<<n/2;
		return 0;
	}
	for(int i=st,k=1;k<=n;k++,i++){
		if(a[i]!=0) cnt+=a[i]+t%2+t/2,t=0;//有小房间就全加起来，再结算前面连续的大房间，最后将大房间的个数清零 
		else t++;//没有小房间的话就累加个数 
	}
	cout<<cnt+t%2+t/2;//输出的时候再算一次防止数组末尾是0导致没算进去 
	return 0;
}
/*
6
3 0 2 0 0 0
*/

The end.