[数据结构与算法]武汉ACM集训——贪心-7

武汉ACM集训——贪心-7

洛谷 P6878 [JOI 2020 Final] JJOOII 2

题解

首先将字符串中各字母的下标按照字母种类分类存储。

接着依次遍历字母 J, O, I 当符合情况时，存储数据。

ans = min{ (右下标 - 左下标 + 1) - (3 x K) }

AC代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
#define inf 0x3f3f3f3f
int mp[4][maxn];

int main()
{
    memset(mp, 0, sizeof(mp));
    int n, k;
    scanf("%d%d", &n, &k);
    string str;
    cin >> str;
    // 存储字符串中字母下标
    int x = 1, y = 1, z = 1;
    for (int i = 0; i < n; ++i)
    {
        if (str[i] == 'J')
            mp[1][x++] = i + 1;
        else if (str[i] == 'O')
            mp[2][y++] = i + 1;
        else
            mp[3][z++] = i + 1;
    }
    bool f = 0;
    int ans = inf;
    // 遍历字母 J
    int tmpx = k, tmpy = k, tmpz = k;
    for (tmpx; tmpx < x; ++tmpx)
    {
        int l = mp[1][tmpx - k + 1];
        // 当找到符合情况的 J 时，遍历字母 O
        for (tmpy; tmpy < y; ++tmpy)
        {
            // 当找到符合情况的 O 时，遍历字母 I
            if (mp[2][tmpy - k + 1] > mp[1][tmpx])
            {
                for (tmpz; tmpz < z; ++tmpz)
                {
                    // 当找到符合情况的 I 时，存储数据 tmpx，tmpy，tmpz
                    // 优化：tmpy 和 tmpz 一定比上一次的大，因此从上一次的位置开始遍历
                    if (mp[3][tmpz - k + 1] > mp[2][tmpy])
                    {
                        f = 1;
                        ans = min(ans, (mp[3][tmpz] - l + 1) - (3 * k));
                        break;
                    }
                }
                break;
            }
        }
    }
    if (f)
        printf("%d", ans);
    else
        printf("-1");
    return 0;
}