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

· · 题解

题解：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.