Codeforces Round #565 (Div. 3)
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 66 and it is possible to split it into k6k6 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,424,8,15,16,23,42);
- [4,8,15,16,23,42,4] (the length of the array is not divisible by 66);
- [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,…,ana1,a2,…,an (each ai is one of the following numbers: 4,8,15,16,23,424,8,15,16,23,42), where ai is the i-th element of aa.
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
题意:
思路:
(题意思路有空再补,orzorz)
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<algorithm> 6 #include<map> 7 #include<set> 8 #include<vector> 9 #include<queue> 10 using namespace std; 11 #define ll long long 12 const int mod=1e9+7; 13 const int inf=1e9+7; 14 15 //const int maxn=; 16 17 queue<int>q[6]; 18 19 ll int cnt=0; 20 21 void solve() 22 { 23 while(!q[0].empty()) 24 { 25 int now=q[0].front(); 26 for(int i=1;i<6;i++) 27 { 28 if(q[i].empty()) 29 { 30 return ; 31 } 32 if(q[i].front()>now) 33 { 34 now=q[i].front(); 35 continue; 36 } 37 else if(q[i].front()<now) 38 { 39 q[i].pop(); 40 while(q[i].front()<now) 41 { 42 if(q[i].empty()) 43 { 44 return ; 45 } 46 q[i].pop(); 47 } 48 now=q[i].front(); 49 } 50 } 51 cnt++; 52 for(int i=0;i<6;i++) 53 q[i].pop(); 54 } 55 } 56 int main() 57 { 58 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 59 int n; 60 cin>>n; 61 int num; 62 for(int i=0;i<n;i++) 63 { 64 cin>>num; 65 if(num==4) 66 q[0].push(i); 67 else if(num==8) 68 q[1].push(i); 69 else if(num==15) 70 q[2].push(i); 71 else if(num==16) 72 q[3].push(i); 73 else if(num==23) 74 q[4].push(i); 75 else if(num==42) 76 q[5].push(i); 77 } 78 79 cnt=0; 80 81 solve(); 82 83 cout<<n-6*cnt<<endl; 84 85 return 0; 86 }