แบ่งช็อกโกแลตเป็นภาษา C++

สมมติว่าเรามีช็อกโกแลตแท่งหนึ่งแท่งที่ประกอบด้วยชิ้นบางชิ้น ในแต่ละชิ้นมีความหวานที่กำหนดโดยรายการที่เรียกว่าความหวาน ถ้าเราต้องการแบ่งช็อกโกแลตให้เพื่อนๆ ชาว K เราเริ่มตัดช็อกโกแลตแท่งเป็นชิ้น K+1 โดยใช้การตัด K ตอนนี้แต่ละชิ้นจะประกอบด้วยชิ้นที่ต่อเนื่องกัน ถ้าเรานำชิ้นที่มีความหวานรวมขั้นต่ำและมอบชิ้นอื่นๆ ให้เพื่อนของเรา เราต้องหาความหวานสูงสุดของชิ้นนั้นโดยการตัดแท่งช็อกโกแลตให้เหมาะสมที่สุด

ดังนั้นหากอินพุตเป็นเหมือนความหวาน =[1,2,3,4,5,6,7,8,9], K =5 ผลลัพธ์จะเป็น 6 เนื่องจากคุณสามารถแบ่งช็อกโกแลตเป็น [1,2 ได้ ,3], [4,5], [6], [7], [8], [9] ชิ้นนี้.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน ok() ซึ่งจะใช้อาร์เรย์ v, cuts, maxVal,

• ตัวนับ :=0, อุณหภูมิ :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <=ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้า temp> =maxVal แล้ว

    • (เพิ่มตัวนับทีละ 1)

    • อุณหภูมิ :=0

  • ถ้าฉันมีขนาดเท่ากับ v แล้ว −

    • ออกจากวง

  • temp :=temp + v[i]

• คืนค่าเป็นจริงเมื่อตัวนับ>=ตัด

• จากวิธีหลัก ให้ทำดังนี้:

• สูงสุด :=-1

• n :=ขนาดของ s

• ต่ำ :=0, สูง :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ต่ำ :=ต่ำสุดของค่าต่ำสุดและ s[i]

  • สูง :=สูง + s[i]

• (เพิ่มขึ้นสูง 1)

• ในขณะที่ต่ำ <สูง ทำ -

  • กลาง :=ต่ำ + (สูง - ต่ำ + 1) / 2

  • ถ้า ok(s, k + 1, mid) เป็นจริง −

    • ต่ำ :=กลาง

  • มิฉะนั้น

    • สูง :=กลาง - 1

• กลับต่ำ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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));
}

อินพุต

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

ผลลัพธ์

6