题解：P15594 [ICPC 2020 Jakarta R] Exchange Bottleneck

ycy25 · 2026-03-04 23:15:39 · 题解

思路

容易看出，如果 E 数组中有一个 1 且前面有 0，那么答案会直接变成 2，因为所有城市都能通过这个城市与其他所有城市相通。

然后来考虑在最后一个 1 之后的 0。这部分形成了一条链，瓶颈为 0 的个数加 1（因为要交换信息的城市也要算进来）。

若 E 数组全为 1 没有 0，答案显然为 1。

注意 E_1 不论是 0 还是 1 都应当成 1 处理。

代码

#include<cstdio>
int main()
{
    int n;
    scanf("%d",&n);
    int now=0,maxn=0,a;
    scanf("%d",&a);//E_1不用处理（此时now=0，不用清空）
    for(int i=2;i<n;i++)
    {
        scanf("%d",&a);
        if(a==0){now++;maxn=1;}//记录最后一段0的长度，并标记为有1出现过
        else now=0;//最后一段0不存在了，清空
    }
    maxn=(maxn>now?maxn:now);//若此时now=0但之前有0出现，答案不应为now+1，而应为maxn+1即2
    printf("%d",maxn+1);
    return 0;
}