题解：AT_icpc2015summer_day4_a Where is the Boundary

题意解析：给定

n

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

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

CPP

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。

至于代码：

CPP

#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;
}

题解：AT_icpc2015summer_day4_a Where is the Boundary

文章操作

相关推荐

评论

题解：AT_icpc2015summer_day4_a Where is the Boundary