Chúng tôi nhận được một số sô cô la có mặt trong các hộp liên tiếp dưới dạng một mảng và số k đại diện cho số học sinh sẽ được phân phát. Nhiệm vụ ở đây là chọn các hộp liên tiếp sao cho tổng số sôcôla có trong chúng có thể được chia đều cho k học sinh. Ngoài ra, chúng tôi phải đảm bảo rằng số lượng sôcôla là tối đa.
Đối với điều này, chúng tôi sẽ duyệt qua mảng từ trái sang phải và bắt đầu cộng số sôcôla và chia tổng cho k. Nếu nó được chia hết với phần dư bằng 0 thì lưu tổng này vào một biến. Khi chúng ta tiến xa hơn, chúng ta lặp lại quá trình này cho đến khi chúng ta có được tổng lớn nhất như vậy. Vấn đề là tìm tổng lớn nhất của mảng con chia hết cho k.
Đầu vào
Choco[]={ 1,2,4,5,2,8,3,5 } k=3 Đầu ra −Số sôcôla tối đa được chia đều cho k học sinh - 5
Giải thích - Mảng con tổng tối đa là {5,2,8}. Tổng số sôcôla là 15. Chia đều thì số sôcôla tối đa cả 3 học sinh nhận được là 5.
Lưu ý - các hộp liên tiếp và các chỉ mục là {3,4,5}
Đầu vào
Choco[] = { 2,3,7,5,4,8,2,6 } k=5 Đầu ra −Số sôcôla tối đa được chia đều cho k học sinh - 7
Giải thích - Mảng con tổng tối đa là {3,7,5,4,8,2,6}. Tổng số sôcôla là 35.
Chia đều thì số sôcôla tối đa mà cả 5 học sinh nhận được là 7.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một mảng số nguyên arr [] chứa một số sô cô la trong các vùng chứa liên tiếp.
-
Số phần tử ‘n’ đại diện cho số hộp.
-
Không. của sinh viên là "k" làm đầu vào.
-
Hàm maxChocolate (int arr [], int n, int k), nhận ba đối số - mảng, kích thước của nó và không. của sinh viên k.
-
Chúng ta sẽ bắt đầu xem qua arr [] từ đầu bằng cách sử dụng vòng lặp for.
-
Lấy hai biến sum và maxSum. Sum lưu trữ tổng các phần tử liên tiếp của mảng con.
-
maxSum được sử dụng để lưu trữ tổng tối đa được tìm thấy cho đến nay.
-
Bên trong vòng lặp for lồng nhau, hãy tiếp tục thêm các phần tử và kiểm tra xem tổng% k có cho phần dư là 0 không.
Ngoài ra nếu tổng này> maxSum, hãy cập nhật maxSum.
-
Giá trị maxSum cuối cùng sẽ có giá trị tối đa là không. sôcôla có thể được chia đều cho k học sinh.
-
Trả về kết quả là maxSum / k là số sôcôla mà mỗi học sinh nhận được.
Ví dụ
#include <stdio.h>
// to find the maximum number
// of chocolates to be distributed equally among
// k students
int maxChocolates(int arr[], int n, int k){
int sum;
int 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;
}
}
// distributed equally among 'k' students
return (maxSum / k);
}
int main(){
int arr[] = { 2, 7, 6, 1, 4, 5 ,5, 3 };
int n =8;
int k =3;
printf("Maximum number of chocolates to be distributed equally among k students: %d ",maxChocolates(arr, n, k));
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Maximum number of chocolates to be distributed equally among k students − 11