Số sô-cô-la tối đa phân chia đều cho k học sinh trong C

Cho số sô-cô-la trong các hộp liên tiếp (dạng mảng) và số k học sinh. Nhiệm vụ: chọn các hộp liên tiếp sao cho tổng sô-cô-la chia hết cho k và tổng này lớn nhất.

Ví dụ

Đầu vào

Choco[] = { 1, 2, 4, 5, 2, 8, 3, 5 }, k = 3

Đầu ra - Sô-cô-la mỗi học sinh: 5

Giải thích - Dãy con liên tiếp: {5, 2, 8} (chỉ số 3,4,5), tổng = 15, 15/3 = 5

Đầu vào

Choco[] = { 2, 3, 7, 5, 4, 8, 2, 6 }, k = 5

Đầu ra - Sô-cô-la mỗi học sinh: 7

Giải thích - Dãy con: {3, 7, 5, 4, 8, 2, 6}, tổng = 35, 35/5 = 7

Phương pháp

• Mảng arr[] chứa số sô-cô-la, n hộp, k học sinh
• Hàm maxChocolates(int arr[], int n, int k)
• Duyệt tất cả dãy con liên tiếp
• Tính tổng, nếu sum % k == 0 và sum > maxSum thì cập nhật
• Trả về maxSum / k

Chương trình mẫu

#include <stdio.h>

int maxChocolates(int arr[], int n, int k) {
    int sum, maxSum = 0;
    for (int i = 0; i < n; i++) {
        sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            if (sum % k == 0 && sum > maxSum)
                maxSum = sum;
        }
    }
    return (maxSum / k);
}

int main() {
    int arr[] = {2, 7, 6, 1, 4, 5, 5, 3};
    int n = 8, k = 3;
    printf("Sô-cô-la mỗi học sinh: %d", maxChocolates(arr, n, k));
    return 0;
}

Kết quả

Sô-cô-la mỗi học sinh: 11

Giải thích: Dãy con tối ưu có tổng 33, chia cho 3 = 11.