AtCoder题解｜Attention

AtCoder题解｜ABC 98C - Attention

---

题目信息 📚

【题目描述】

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 $S_i = E$, and west if $S_i = 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.

【输入】

The input is given from Standard Input in the following format:

$N$

$S$

【输出】

Print the minimum number of people who have to change their directions.

【数据范围】

• $2 \le N \le 3 \times 10^5$
• $|S| = N$
• $S_i$ is E or W.

【输入样例1】

5
WEEWW

【输出样例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$.

【输入样例2】

12
WEWEWEEEWWWE

【输出样例2】

4

【输入样例3】

8
WWWWWEEE

【输出样例3】

3

【题目来源】

https://atcoder.jp/contests/abc098/tasks/arc098_a

---

题目解析 🍉

【题目分析】

前缀数组预处理来进行时间复杂度优化。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n, cnt, pre[N], back[N];
string s;

int main() {
    cin >> n >> s;

    // 前缀数组，pre[i]统计1~i中共有多少个'E'
    for (int i = 1; i <= s.size(); i++) {
        pre[i] = (s[i - 1] == 'E' ? 1 : 0);
        pre[i] += pre[i - 1];
    }

    // 后缀数组，back[i]统计i+1~n中共有多少个'W'
    for (int i = s.size(); i >= 1; i--) {
        back[i] = (s[i - 1] == 'W' ? 1 : 0);
        back[i] += back[i + 1];
    }

    int ans = INT_MAX;
    for (int i = 1; i <= s.size(); i++) {
        // 选取第i个人为leader
        cnt = (i - 1) - pre[i - 1]; // 1~i-1均需变成'E'
        cnt += (n - i) - back[i + 1]; // i+1~n均需变成'W'
        ans = min(ans, cnt);
    }
    cout << ans << endl;


    return 0;
}

---

【Pythoon代码】

左、右前缀

from sys import stdin

input = lambda: stdin.readline()[:-1]

# 读入字符串
n = int(input())
s = input()

# 左前缀数组
l = [0] * n
for i in range(1, n):
    l[i] = l[i - 1] + (1 if s[i - 1] == 'W' else 0)

# 右前缀数组
r = [0] * n
for i in range(n - 2, -1, -1):
    r[i] = r[i + 1] + (1 if s[i + 1] == 'E' else 0)

# 输出最小值
res = min(l[i] + r[i] for i in range(n))
print(res)

另一种思路

# Python快读
from sys import stdin
input = lambda: stdin.readline()[:-1]

def main():
    n = int(input())
    s = input()
    tmp = s[1:].count('E')
    res = tmp
    for i in range(1, n):
        tmp = tmp - (1 if s[i] == 'E' else 0)
        tmp = tmp + (1 if s[i-1] == 'W' else 0)
        res = min(res, tmp)
    print(res)

if __name__ == '__main__':
    main()