Chia sẻ socola trong C++

Giả sử chúng ta có một thỏi socola bao gồm một số miếng. Trong mỗi miếng có độ ngọt riêng cho bởi danh sách gọi là sweetness. Nếu chúng ta muốn chia sẻ socola cho K bạn bè nên bắt đầu cắt thỏi socola thành K+1 mảnh dùng K lần cắt, bây giờ mỗi mảnh bao gồm một số miếng liên tiếp. Nếu chúng ta lấy mảnh có tổng độ ngọt nhỏ nhất và cho các mảnh còn lại cho bạn bè. Chúng ta phải tìm tổng độ ngọt lớn nhất của mảnh chúng ta có thể được bằng cách cắt thỏi socola tối ưu.

Vì vậy, nếu đầu vào là sweetness = [1,2,3,4,5,6,7,8,9], K = 5, đầu ra sẽ là 6 vì bạn có thể chia socola thành [1,2,3], [4,5], [6], [7], [8], [9] các mảnh này.

Để giải quyết, chúng ta sẽ làm theo các bước:

Định nghĩa hàm ok(), nhận mảng v, cuts, maxVal,
counter := 0, temp := 0
Khởi tạo i := 0, khi i <= kích thước v, cập nhật (tăng i lên 1), làm:
- nếu temp >= maxVal, thì
  - (tăng counter lên 1)
  - temp := 0
- nếu i giống kích thước v, thì:
  - Thoát khỏi vòng lặp
- temp := temp + v[i]
Trả về true khi counter >= cuts
Từ phương thức main làm sau:
maxa := -1
n := kích thước s
low := 0, high := 0
Khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), làm:
- low := nhỏ nhất của low và s[i]
- high := high + s[i]
(tăng high lên 1)
Khi low < high, làm:
- mid := low + (high - low + 1) / 2
- nếu ok(s, k + 1, mid) đúng, thì:
  - low := mid
- Ngược lại
  - high := mid - 1
Trả về low

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    bool ok(vector <int> v, int cuts, int maxVal){       int counter = 0;       int temp = 0;       for (int i = 0; i <= v.size(); i++) {          if (temp >= maxVal) {             counter++;             temp = 0;          }          if (i == v.size()) {             break;          }          temp += v[i];       }       return counter >= cuts;    }    int maximizeSweetness(vector<int>& s, int k) {       int maxa = -1;       int n = s.size();       int low = 0;       int high = 0;       for (int i = 0; i < n; i++) {          low = min(low, s[i]);          high += s[i];       }       high++;       while (low < high) {          int mid = low + (high - low + 1) / 2;          if (ok(s, k + 1, mid))             low = mid;          else             high = mid - 1;       }       return low;    } }; main(){    Solution ob;    vector<int> v = {1,2,3,4,5,6,7,8,9};    cout << (ob.maximizeSweetness(v, 5)); }

Đầu vào

{1,2,3,4,5,6,7,8,9}, 5

Chia sẻ socola trong C++

Ví dụ

Đầu vào

Đầu ra