Dãy đẹp

Xem dạng PDF
Gửi bài giải
Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: DAYDEP.INP
Output: DAYDEP.OUT
Tác giả:
bedao
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Hãy đọc nội quy trước khi bình luận.


  • 0
    HaDat_Python  đã bình luận lúc 25, Tháng 12, 2025, 1:13

    include <bits/stdc++.h>

    using namespace std;

    int main() { ios::syncwithstdio(false); cin.tie(nullptr); freopen("DAYDEP.INP", "r", stdin); freopen("DAYDEP.OUT", "w", stdout); int n; cin >> n; map<long long, long long> freq;

    for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    freq[x]++;
}

long long ans = 0;

for (auto &p : freq) {
    long long x = p.first;
    long long c = p.second;

    if (c == x) continue;
    else if (c > x) ans += c - x;
    else ans += c;
}

cout << ans;
return 0;

    }


  • 0
    dtnguyenthehung  đã bình luận lúc 19, Tháng 10, 2025, 8:17

    from collections import Counter

    Đọc input từ file

    with open("DAYDEP.INP", "r") as f: n = int(f.readline()) a = list(map(int, f.readline().split()))

    count = Counter(a) delete_count = 0

    for x in count: freq = count[x] if freq == x: continue elif freq > x: deletecount += freq - x else: # freq < x deletecount += freq

    Ghi output

    with open("DAYDEP.OUT", "w") as f: f.write(str(delete_count)) CODE PYTHON CHO MỌI NGƯỜI THAM KHẢO NHÉ


  • 0
    pvpccuatoi  đã bình luận lúc 12, Tháng 8, 2025, 9:55

    with open('DAYDEP.INP','r') as f: dat = f.read().split('\n') n = int(dat[0]) l = list(map(int,dat[1].split())) from collections import Counter x = Counter(l) d = 0 for i,val in x.items(): if i < val: d += val - i elif i > val: d += val print(d) with open('DAYDEP.out','w') as f: f.write(str(d))


  • 0
    meo8110b  đã bình luận lúc 8, Tháng 8, 2025, 5:38

    Bác nào bí quá có thể tham khảo thử

    dùng một unordered_map để đếm số lần xuất hiện của các phần tử, tạm gọi là a

    tạo một biến để lưu kết quả, giá trị =0, tạm gọi là biến res

    duyệt qua các phần tử trong a bằng for (dùng auto i:a) để tiện hơn. Tính kết quả như sau : Nếu như số lần xuất hiện nhỏ hơn giá trị phần tử đó thì res+= số lần xuất hiện. Ngược lại nếu lớn hơn thì res += số lần xuất hiện-giá trị


  • 3
    Terence  đã bình luận lúc 10, Tháng 5, 2025, 15:49

    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


    • 0
      quanbrocode2704  đã bình luận lúc 28, Tháng 9, 2025, 16:55

      thật ra là ô chỉ cần mảng tần suất thôi là quá đủ rồi, tại vì key chỉ là dạng số nên chả cần đến map


    • -1
      lanMX  đã bình luận lúc 6, Tháng 6, 2025, 8:04

      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


      • 0
        meo8110b  đã bình luận lúc 8, Tháng 8, 2025, 5:41

        ở đoạn mà 

        else res-= p.second-p.first;

        bạn thay bằng 

        else res+=p.second-p.first;

        là được nhé