Dãy đẹp
Xem dạng PDF
Dãy số ~b_1, b_2, ..., b_k~ được gọi là dãy đẹp nếu thỏa mãn điều kiện sau: với mỗi giá trị ~b_i~ trong dãy, số lần xuất hiện của nó trong dãy là đúng ~b_i~ lần.
Ví dụ: Dãy ~4, 4, 1, 2, 4, 2, 4~ là dãy đẹp vì giá trị ~4~ xuất hiện ~4~ lần, ~1~ xuất hiện ~1~ lần, ~2~ xuất hiện ~2~ lần. Dãy ~2, 5, 1, 2~ là không phải là dãy đẹp vì ~5~ xuất hiện ~1~ lần.
Yêu cầu: Cho dãy số nguyên gồm ~N~ phần tử ~a_1, a_2,….a_N~. Tìm số phần tử ít nhất cần xóa khỏi dãy để dãy trở thành dãy đẹp?
Input
Vào từ tệp văn bản DAYDEP.INP:
Dòng 1 chứa số nguyên dương ~N~ (~1 \leq N \leq 10^5~)
Dòng 2 chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~0 \leq a_i \leq 10^6~)
Output
Đưa ra tệp DAYDEP.OUT một số duy nhất là số lượng số ít nhất cần xóa để dãy trở thành dãy đẹp.
Sample Input 1
5
2 5 1 2 5
Sample Output 1
2
Notes
Giải thích : xóa ~2~ số ~5~ thì dãy còn ~3~ phần tử ~2, 1, 2~ là dãy đẹp
Bình luận
For: phunguyengia0809
*Sử dụng map đếm phân phối *
Gọi res là kết quả cần tìm.
Gọi val, freq là cặp giá trị trong map.
Ta xét các trường hợp:
Nếu freq = val: continue
Nếu freq > val: res += freq - val
Cón lại: res += freq
pragma GCC optimize("03,unroll-loops")
pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
include <bits/stdc++.h>
define ll long long
using namespace std; signed main() { freopen("DAYDEP.INP", "r", stdin); freopen("DAYDEP.OUT", "w", stdout);iosbase::syncwithstdio(false);cin.tie(0);cout.tie(0); unorderedmap<long long ,long long> mp; long long n,res=0; cin>>n; vector<long long> a(n); for (long long i=0;i<n;i++){cin>>a[i];mp[a[i]]++;} for (auto &p:mp){ if (p.first==p.second) continue; else if (p.first>p.second) res+=p.second; else res-=p.second-p.first; } cout<<res; } debug ho e voi cac cao nhan