Codeforces Round #378 (Div. 2)

题目链接：https://codeforces.com/contest/733

A - Grasshopper And the String

题意：有个虫子，要跳过一个长度为 \(n\) 的字符串（从 \(0\) 跳到 \(n+1\) ），只能停在元音字母处。求最短的跳跃距离。

题解：求前后相邻两个停留位置的差的最大值。

char s[200005];

void test_case() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    int lst = 0, maxlen = 0;
    for(int i = 1; i <= n; ++i) {
        if(s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U' || s[i] == 'Y') {
            maxlen = max(maxlen, i - lst);
            lst = i;
        }
    }
    maxlen = max(maxlen, n + 1 - lst);
    printf("%d\n", maxlen);
}

B - Parade

题意：阅兵，第 \(i\) 行的士兵有 \(l_i\) 个喜欢先出左脚，有 \(r_i\) 个喜欢先出右脚。定义阅兵的整齐度为 \(|L-R|\) ，其中 \(L=\sum_{i=1}^{n}l_i\) ，
\(R\) 同理。现在可以调整至多一个行的士兵，让他们左右颠倒，求最大的整齐度。

题解：枚举这个行。

int n;
int l[100005];
int r[100005];

void test_case() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &l[i], &r[i]);
    ll sumL = 0, sumR = 0;
    for(int i = 1; i <= n; ++i) {
        sumL += l[i];
        sumR += r[i];
    }
    int ans = 0;
    ll cur = abs(sumL - sumR);
    ll tsumL = sumL, tsumR = sumR;
    for(int i = 1; i <= n; ++i) {
        sumL -= l[i];
        sumR -= r[i];
        sumL += r[i];
        sumR += l[i];
        ll tmp = abs(sumL - sumR);
        if(tmp > cur) {
            ans = i;
            cur = tmp;
        }
        sumL = tsumL;
        sumR = tsumR;
    }
    printf("%d\n", ans);
}

Codeforces Round #378 (Div. 2)

原文：https://www.cnblogs.com/KisekiPurin2019/p/12274986.html