题解：AT_icpc2015summer_day4_a Where is the Boundary

· · 题解

AT_icpc2015summer_day4_a Where is the Boundary 题解

题目大意

给定 n 个县和每个县的文化标记（W 或 E），需要选择一个边界，使得在这个边界左边的县标记为 W 的数量与右边的县标记为 E 的数量之和最小。

思路

首先读取县的数量 n 和每个县的文化标记字符串，并统计所有县中 W 的总数量。

对于每个可能的边界位置（即在每两个县之间的位置），分别计算左边的 W 数量和右边的 E 数量。

左边的 W 数量在遍历过程中会增加，而右边的 E 数量则会随着边界的变化而减少。

通过维护两个变量，分别记录当前左边的 W 数量和右边的 E 数量，并在每次边界移动时更新这两个数量。

在遍历所有边界位置时，记录最小的 W 数量加上右边的 E 数量之和，以及对应的边界位置。

最终输出最小值对应的边界位置即可。

Code

#include <bits/stdc++.h>
using namespace std;

int n,m,x=0,y=0;

int main() {
    cin>>m>>n;  // 输入县的数量和每个县的文化标记的长度
    string s[n];

    // 读取县的文化标记，并统计总的W数量
    for(int i=0;i<n;i++) {
        cin>>s[i];
        for(int j=0;j<m;j++)
            if(s[i][j]=='W')
                y++;  // 统计W的数量
    }

    int a=0,b=1;  // 用于记录最佳边界的位置
    int M=y;  // 初始化最小错误数为总的W数量

    // 遍历每个可能的边界
    for(int j=0;j<m;j++) {
        for(int i=0;i<n;i++)
            s[i][j]=='W'?y--:x++;  // 更新W和E的数量

        // 计算当前边界的错误数量
        if(x+y<M) {
            M=x+y;  // 更新最小错误数
            a=j+1;  // 记录边界位置
            b=j+2;  // 下一个边界位置
        }
    }

    cout<<a<<" "<<b<<'\n';  // 输出结果
    return 0;
}