Codeforces题解｜1176C - Lose it!

题目信息 📚

【题目描述】

You are given an array $a$ consisting of $n$ integers. Each $a_i$ is one of the six following numbers: $4, 8, 15, 16, 23, 42$.

Your task is to remove the minimum number of elements to make this array good.

An array of length $k$ is called good if $k$ is divisible by $6$ and it is possible to split it into $\frac{k}{6}$ subsequences $4, 8, 15, 16, 23, 42$.

Examples of good arrays:

$[4, 8, 15, 16, 23, 42]$ (the whole array is a required sequence);
$[4, 8, 4, 15, 16, 8, 23, 15, 16, 42, 23, 42]$ (the first sequence is formed from first, second, fourth, fifth, seventh and tenth elements and the second one is formed from remaining elements);
$[]$ (the empty array is good).

Examples of bad arrays:

$[4, 8, 15, 16, 42, 23]$ (the order of elements should be exactly $4, 8, 15, 16, 23, 42$);
$[4, 8, 15, 16, 23, 42, 4]$ (the length of the array is not divisible by $6$);
$[4, 8, 15, 16, 23, 42, 4, 8, 15, 16, 23, 23]$ (the first sequence can be formed from first six elements but the remaining array cannot form the required sequence).

【输入】

The first line of the input contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ (each $a_i$ is one of the following numbers: $4, 8, 15, 16, 23, 42$), where $a_i$ is the $i$-th element of $a$.

【输出】

Print one integer — the minimum number of elements you have to remove to obtain a good array.

【输入样例1】

5
4 8 15 16 23

【输出样例1】

【输入样例2】

12
4 8 4 15 16 8 23 15 16 42 23 42

【输出样例2】

【输入样例3】

15
4 8 4 8 15 16 8 16 23 15 16 4 42 23 42

【输出样例3】

【题目来源】

https://codeforces.com/problemset/problem/1176/C

题目解析 🍉

【题目分析】

思维 + 统计

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int a[N], n;
map<int, int> mp;

// 查找离散化下标
int findi(int x) {
    int t[6] = {4, 8, 15, 16, 23, 42};
    return lower_bound(t, t + 6, x) - t + 1;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        // 逐个读入元素
        cin >> a[i];
        int id = findi(a[i]);
        mp[id]++;

        // 判断当前元素，是否有合法个前置元素
        // 如当前读到15，且map[findi(15)]=3，说明共有3个15
        // 则前面至少有3个4和8，该15才合法
        for (int i = 1; i < id; i++) {
            if (mp[i] < mp[id]) {
                mp[id]--;
                break;
            }
        }
    }

    // 输出答案
    int cnt = 0x3f3f3f3f;
    for (int i = 1; i <= 6; i++) {
        cnt = min(cnt, mp[i]);
    }
    cout << n - cnt * 6 << endl;

    return 0;
}