C++ Bài 12.F2: Lớp học buồn ngủ

Submit solution
Points: 40 (partial)
Time limit: 1.0s
Memory limit: 20M
Author:
buitrunghieu
Problem type

Thầy Hiếu vừa quay trở lại giảng dạy trực tiếp sau một thời gian dài. Tuy nhiên, thầy thường xuyên giảng bài một cách nhàm chán, khiến Bảo, học sinh của thầy, thường xuyên ngủ gật trong lớp. Thầy Hiếu đã nhận thấy điều này và yêu cầu Mắm, chú mèo thông minh trong lớp, ghi chép lại số lần Bảo ngủ gật trong mỗi tiết học. Có \(N\) tiết học \((1≤N≤10^5)\), và Mắm ghi chép rằng Bảo ngủ gật \(a_i\) lần \((0≤a_i≤10^6)\) trong tiết học thứ \(i\). Tổng số lần Bảo ngủ gật trong tất cả các tiết học là không quá \(10^6\).

Mắm, muốn khiến thầy Hiếu cảm thấy rằng Bảo luôn ngủ gật một số lần như nhau trong mỗi tiết học - làm cho vấn đề hoàn toàn là lỗi của Bảo, không phụ thuộc vào việc giảng dạy đôi khi nhàm chán của thầy Hiếu. Cách duy nhất Mắm có thể chỉnh sửa nhật ký là bằng cách kết hợp hai tiết học liền kề. Ví dụ, nếu \(a=[1,2,3,4,5]\), thì nếu Mắm kết hợp hai tiết học thứ hai và thứ ba, nhật ký sẽ trở thành \([1,5,4,5]\).

Hãy giúp Mắm tính toán số lượng chỉnh sửa tối thiểu cần thiết để cô ấy có thể làm cho tất cả các số trong nhật ký bằng nhau.

INPUT FORMAT

Mỗi đầu vào sẽ chứa \(T(1≤T≤10)\) trường hợp cần giải quyết độc lập.
Dòng đầu tiên chứa \(T\), số lượng trường hợp cần giải quyết. Tiếp theo là \(T\) trường hợp, mỗi trường hợp được mô tả bởi một cặp dòng. Dòng đầu tiên của mỗi cặp chứa \(N\), và dòng thứ hai chứa \(a_1,a_2,\dots,a_N\).

Được đảm bảo rằng trong mỗi trường hợp, tổng tất cả các giá trị trong a là không quá \(10^6\). Cũng được đảm bảo rằng tổng của \(N\) trên tất cả các trường hợp là không quá \(10^5\)

OUTPUT FORMAT

Hãy in ra \(T\) dòng đầu ra, chỉ ra số lượng chỉnh sửa tối thiểu mà Mắn có thể thực hiện để làm cho tất cả các mục nhật ký bằng nhau cho mỗi trường hợp.

Ví dụ:

Input
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0
Output
3
2
0

Trong trường hợp đầu tiên của ví dụ, Mắn có thể thay đổi nhật ký của mình để chỉ gồm các số \(3\) với \(3\) chỉnh sửa.
1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3
Trong trường hợp thứ 2 của ví dụ, Mắn có thể thay đổi nhật ký của mình để chỉ gồm các số \(7\) với \(2\) chỉnh sửa.
2 2 3
-> 2 5
-> 7

Giải thích ví dụ mẫu:

  • Ví dụ 1:

    • Để làm cho tất cả các số trong nhật ký bằng nhau, cần thực hiện 3 chỉnh sửa, ví dụ: 1 2 3 1 1 1 -> 3 3 1 1 1 -> 3 3 2 1 -> 3 3 3.

  • Ví dụ 2:

    • Để tất cả các số trong nhật ký bằng nhau, cần thực hiện 2 chỉnh sửa, ví dụ: 2 2 3 -> 2 5 -> 7.


Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House

Comments


  • 0
    endc67_fullhouse_dev  commented on Jan. 5, 2025, 6:21 a.m. 
    /*
    By HoVuVietTruong
    05/01/2024
*/
#include <bits/stdc++.h>
using namespace std;

int a[200003];
int n;

bool check(int m)
{
    int s = 0;
    for (int i = 1; i <= n; i++)
    {
        s += a[i];
        if (i == n && s != m) return false;
        if (s == m) s = 0;
        if (s > m) return false;
    }

    return true;
}


void solve()
{

    cin >> n;


    int s = 0;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        s+= a[i];
    }

    if (s == 0) {
        cout << 0 <<'\n';
        return;
    }

    vector<int> v;

    for (int i = 1; i <= s;i++)
    if (s % i == 0) v.push_back(i);

    int ans = 1e6;
    for (auto e : v)
    {
        int res = 0;
        bool ok = check(e);
        if (ok)
        {
            int cnt = 0, sum = 0;
            for (int i = 1; i <= n; i++)
            {
                sum += a[i];
                cnt++;
                if (sum == e) 
                {
                    res += cnt - 1;
                    sum = 0;
                    cnt = 0;
                }
            }
            ans = min(ans, res);
        }
    }

    cout << ans << '\n';

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) solve();

}
Zalo