Lose it! CodeForces - 1176C 문제 해결

Lose it! CodeForces - 1176C

제목

분석

코드

전송문

제목.
You are given an array a consisting of n integers. Each ai 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 k6 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). Input The first line of the input contains one integer n (1≤n≤5⋅105) — the number of elements in a.
The second line of the input contains n integers a1,a2,…,an (each ai is one of the following numbers: 4,8,15,16,23,42), where ai is the i-th element of a.
Output Print one integer — the minimum number of elements you have to remove to obtain a good array.
Examples Input

5
4 8 15 16 23

Output

5

Input

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

Output

0

Input

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

Output

3

분석하다.
이 문제의 관건은 [4,8.15.16.23.42] 서열을 구성할 수 있는 개수를 구하는 데 있다. 주의해야 할 것은 모든 자모의 순서가 바뀌면 안 된다는 것이다. 여기서 나는 맵을 이용하여 이 숫자들을 비추어 계산하기 편리하게 한 다음에 한 숫자를 입력할 때마다 판단을 하고 앞의 숫자의 개수가 입력한 숫자의 개수보다 항상 많다는 것을 보장한다.
자, 구체적인 문제풀이 과정은 제 코드를 볼 수 있고 상세한 코드 주석이 있습니다~
코드

#include
#include
using namespace std;

map<int, int> mp;

int main()
{
	int n;
    cin >> n;
    mp[4] = 0;
    mp[8] = 1;
    mp[15] = 2;
    mp[16] = 3;
    mp[23] = 4;
    mp[42] = 5;
    int ans[6] = {0}; //        

    for (int i = 0;i < n;i++)
    {
        int a;
        cin >> a;
        if (mp[a] == 0){
			ans[mp[a]]++;
		}else if (ans[mp[a]-1]>0) //          ，       。   ans[0,4]       ，             
        {
            ans[mp[a]-1]--; //             
            ans[mp[a]]++;
        }
    }
    cout << n-6*ans[5] << endl; //                      

    return 0;
}

전송문
Lose it! CodeForces - 1176C