题解：AT_icpc2015summer_day4_a Where is the Boundary

_CKX001_ · 2024-12-28 23:26:05 · 题解

题意解析：给定 n 个县和每个县的标记（W 或 E）（不止一个标记），选择一个边界，使得在这个边界左边的县标记为 W 的数量与右边的县标记为 E 的数量之和最小，且需要输出编号最小的结果。

解题思路：按照文案读入输入输出，即：

n m
d[1]  ···  d[n]
···
d[m1] ··· d[mn]

数据范围小得可怜，n\le10000，m\le100。看到这个我就想到了直接暴搜，遍历在每两个县之间的位置，分别计算这个位置左边的 W 数量和右边的 E 数量，与之前最优状态进行比较，如果更小意味着方案更优，就要更新状态，并且更新最优状况的横轴和竖轴的位置。变量就用一个 w 存储 W 的数量，再用一个 e 存储 E 的数量，用 ans 来存储当前最优状态时的和，以及 x 和 y 分别存储最优状况的横轴和竖轴的位置。代码中直接用小于是因为从做开始最先遍历到的一定最优。string下标从 0 开始所以for中初始值应为 0。

至于代码：

#include<bits/stdc++.h>            
using namespace std;               
int main(){
    string d[10004];
    int n,m,x=0,y=1,w=0,e=0;
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>d[i];
        for(int j=0;j<m;j++){
            if(d[i][j]=='W'){
                w++;                
            }
        }
    }            
    int ans=w;                        
    for(int j=0;j<m;j++){           
        for(int i=0;i<n;i++){
            if(d[i][j]=='W'){        
                w--;
            }
            else if(d[i][j]=='E'){
                e++;
            }
        }
        if(w+e<ans){
            ans=w+e;              
            x=j+1;               
            y=j+2;               
        }

    }
    cout<<x<<" "<<y<<endl;
    return 0;
}