ARC 098 C - Attention
Problem Statement
There are N people standing in a row from west to east. Each person is facing east or west. The directions of the people is given as a string S of length N. The i-th person from the west is facing east if Si= E
, and west if Si= W
.
You will appoint one of the N people as the leader, then command the rest of them to face in the direction of the leader. Here, we do not care which direction the leader is facing.
The people in the row hate to change their directions, so you would like to select the leader so that the number of people who have to change their directions is minimized. Find the minimum number of people who have to change their directions.
Constraints
- 2≤N≤3×105
- |S|=N
- Si is
E
orW
.
Input
Input is given from Standard Input in the following format:
N
S
Output
Print the minimum number of people who have to change their directions.
Sample Input 1
5
WEEWW
Sample Output 1
1
Assume that we appoint the third person from the west as the leader. Then, the first person from the west needs to face east and has to turn around. The other people do not need to change their directions, so the number of people who have to change their directions is 1 in this case. It is not possible to have 0 people who have to change their directions, so the answer is 1.
Sample Input 2
12
WEWEWEEEWWWE
Sample Output 2
4
Sample Input 3
8
WWWWWEEE
Sample Output 3
3 模拟题
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#define ll long long
using namespace std;
const int maxn=300005; int n,qz[maxn],tot,ans=1<<30;
char s[maxn]; int main(){
scanf("%d",&n),scanf("%s",s+1);
for(int i=1;i<=n;i++) qz[i]=qz[i-1]+(s[i]=='E');
tot=qz[n];
for(int i=1;i<=n;i++) ans=min(ans,(i-1-qz[i-1])+(tot-qz[i]));
cout<<ans<<endl;
return 0;
}
最新文章
- LeetCode 299 Bulls and Cows
- Openstack Basic
- Entity Framework优缺点及使用方法总结
- 《SQL Server企业级平台管理实践》读书笔记——SQL Server中收缩数据库不好用的原因
- 第十周java 学习总结
- java web 学习八(HttpServletResponse对象2)
- [转] 再叙TIME_WAIT
- Android 跨应用调用Activity及Service
- Cocos2d-x 3.x plist+png 做动画
- Canvas的quadraticCurveTo 和 bezierCurveTo 画曲线 方法细说
- (Chrome42)Lodop总计页面提示“未安装”要么“请升级”可能的原因和解决方案
- 【转】python - PyDev统一编码
- NodeJs的简单介绍
- Java 8 Stream介绍及使用2
- .netcore 读取ansi编码
- FORTH 发展(部分)
- 微信小程序-解决下拉刷新报错
- ServletContextListener中的方法contextInitialized执行了两次
- HashTable和HashMap的区别详解(转)
- web页面font-family显示