c++, tìm kiếm nhị phân Bài 9. Đếm tần số file: COUNT.CPP Cho trước một dãy N phần tử A1, A2, , AN và một số nguyên dương k. Bạn được phép chọn bất kỳ một

Câu hỏi :

c++, tìm kiếm nhị phân Bài 9. Đếm tần số file: COUNT.CPP Cho trước một dãy N phần tử A1, A2, , AN và một số nguyên dương k. Bạn được phép chọn bất kỳ một phần tử nào đó trong dãy và tăng nó lên 1 đơn vị. Bạn được thực hiện phép thay đổi trên không quá k lần (tức là có thể không cần dùng hết k lần). Nhiệm vụ của bạn là tìm ra phần tử xuất hiện nhiều nhất trong dãy sau khi đã thực hiện các phép thay đổi như trên. INPUT: COUNT.INP Dòng đầu tiên chứa hai số nguyên dương N và k (1 n 105; 0 k 109) Dòng thứ hai chứa N số nguyên, mỗi số có giá trị tuyệt đối nhỏ hơn hoặc bằng 109. OUTPUT: COUNT.OUT Chứa hai số nguyên dương t và c, trong đó t là số lần xuất hiện nhiều nhất của c trong dãy A, nếu có nhiều phương án thay đổi thì hãy đưa ra phương án có giá trị bé nhất xuất hiện nhiều lần nhất. Ví dụ: COUNT.INP COUNT.OUT 5 3 6 3 4 0 2 3 4 3 4 5 5 5 3 5 5 3 3 1 2 2 1 4 2 * Giải thích ví dụ 2: Có 2 phương án biến đổi: - Không thay đổi gì ta được kết quả là 3 5 - Thay đổi cả 3 giá trị được kết quả là 3 6 Tuy nhiên 5 nhỏ hơn 6 nên kết quả là 3 5

Lời giải 1 :

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,x;
int dl,dr,c,l,r;
signed main() {
    cin>>n>>k;
    int a[n];
    for (int i=0;i<n;i++) {
        cin>>a[i];
    }
    sort(a,a+n);
    l=0,r=n-1,c=0;
    while (l<r&&c<k) {
        dl=a[l+1]-a[l];
        dr=a[r]-a[r-1];
        if ((l+1)*dl<=(n-r)*dr&&c+(l+1)*dl<=k) {
            c+=(l+1)*dl;
            l++;
        } else if ((l+1)*dl>(n-r)*dr&&c+(n-r)*dr<=k) {
            c+=(n-r)*dr;
            r--;
        } else {
            break;
        }
    }
    cout <<l-r+1<<" "<<a[(l+r)/2]<<'\n';
    return 0;
}

Bạn có biết?

Tin học là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng. Tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin. Hãy tận dụng sức mạnh của tin học để giải quyết các vấn đề và sáng tạo ra những giải pháp mới!

Nguồn :

Wikipedia - Bách khoa toàn thư

Tâm sự lớp 10

Lớp 10 - Năm đầu tiên ở cấp trung học phổ thông, chúng ta sẽ có nhiều bạn bè mới đến từ những nơi khác nhau. Ngôi trường mới, xa nhà hơn, mở ra một thế giới mới với nhiều điều thú vị. Hãy mở lòng đón nhận và tận hưởng những trải nghiệm mới!

Nguồn :

sưu tập

c++, tìm kiếm nhị phân Bài 9. Đếm tần số file: COUNT.CPP Cho trước một dãy N phần tử A1, A2, , AN và một số nguyên dương k. Bạn được phép chọn bất kỳ một

Lời giải 1 :

Bạn có biết?

Nguồn :

Tâm sự lớp 10

Nguồn :

Có thể bạn quan tâm