קאַפּאַציטעט צו שיקן פּאַקידזשיז ין די טעג Leetcode סאַלושאַן


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן
מענגע ביינערי זוכן

פּראָבלעם דערקלערונג

אין דעם פּראָבלעם "קאַפּאַציטעט צו שיקן פּאַקידזשיז ין די טעג," מיר האָבן פּאַקיץ אין פּאָרט א וואָס מוזן זיין טראַנספערד צו פּאָרט ב אין די טעג.

מיר באַקומען אַ ווייץ מענגע וואָס כּולל די וואָג פון יעדער פּאַקאַט און די נומער פון טעג וואָס מיר דאַרפֿן צו אַריבערפירן די פּאַקיץ. אונדזער אַרבעט איז צו געפֿינען די מינימום מאַסע קאַפּאַציטעט פון די שיף צו זיין געניצט צו אַריבערפירן פּאַקיץ פון פּאָרט א צו פּאָרט ב אין די טעג.

לעעטקאָדע לייזונג צו קאַפּאַציטעט צו שיקן פּאַקידזשיז ין די טעג

בייַשפּיל

weights = [1,2,3,4,5,6,7,8,9,10], D = 5
15

דערקלערונג: די שיף וועט אַריבערפירן די פּאַקיץ אויף די פאלגענדע וועג:

ערשטער-טאָג: 1,2,3,4,5

צווייטע טאָג 2: 6,7

דריט-טאָג 3: 8

פערט-טאָג 4: 9

פינפט-טאָג 5:10

אין דעם וועג, די מינימום מאַסע קאַפּאַציטעט פון דער שיף זאָל זיין 15 צו אַריבערפירן אַלע פּאַקיץ אין 5 טעג.

צוגאַנג פֿאַר קאַפּאַציטעט צו שיף פּאַקידזשיז אין די טעג Leetcode סאַלושאַן

דער ערשטער און די מערסט וויכטיק זאַך צו סאָלווע דעם פּראָבלעם איז צו ברענגען אַבזערוויישאַנז. דאָ זענען עטלעכע אַבזערוויישאַנז פֿאַר אונדזער זוכן מעהאַלעך:

  1. די מאַסע קאַפּאַציטעט פון דער שיף זאָל זיין בייַ מינדסטער גלייַך צו די פּאַקאַט מיט די מאַקסימום וואָג אַז איז מאַקס (ווייץ). לאָזן אונדז נאָמען עס ווי אָנהייב.
  2. מיר קענען באַגרענעצן די מאַקסימום קאַפּאַציטעט פון דער שיף צו די סומע פון ​​די וואָג פון אַלע פּאַקיץ וואָס איז סומע (ווייץ). לאָזן אונדז נאָמען עס ווי עק.

איצט מיר האָבן אונדזער זוכן מעהאַלעך. רעכן די גרייס פון די מעהאַלעך איז לענג און די נומער פון פּאַקיץ איז n.  די נאַיוו צוגאַנג קען זיין צו קאָנטראָלירן פֿאַר יעדער ווערט אין די מעהאַלעך אויב די מאַסע קאַפּאַציטעט קענען אַריבערפירן די פּאַקיץ הצלחה אין די טעג און קלייַבן די מינימום פון זיי. די צייט קאַמפּלעקסיטי פֿאַר די נאַיוו צוגאַנג וועט זיין Length * n.

מיר קענען פֿאַרבעסערן די צייט קאַמפּלעקסיטי דורך ביינערי זוך אין אָרט פון לינעאַר זוך.

די צייַט קאַמפּלעקסיטי ניצן די ביינערי זוכן צוגאַנג וועט זיין קלאָץ (Length) * n.

ימפּלעמענטאַטיאָן

C ++ קאָד פֿאַר קאַפּאַציטעט צו שיקן פּאַקידזשיז ין די טעג Leetcode סאַלושאַן

#include <bits/stdc++.h>
using namespace std; 
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4,5,6,7,8,9,10}; 
 int d=5;                               

 cout<<shipWithinDays(arr,d)<<endl;
 return 0;
}
15

Java קאָד פֿאַר קאַפּאַציטעט צו שיקן פּאַקידזשיז אין די טעג Leetcode סאַלושאַן

public class Tutorialcup {
    public static int shipWithinDays(int[] weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5,6,7,8,9,10}; 
     int d=5; 
    int ans= shipWithinDays(arr,d);
    System.out.println(ans);
  }
}
15

קאַמפּלעקסיטי אַנאַליסיס פון קאַפּאַציטעט צו שיף פּאַקידזשיז אין די טעג Leetcode סאַלושאַן

צייט קאַמפּלעקסיטי

די צייט קאַמפּלעקסיטי פון די אויבן קאָד איז אָ (n * קלאָץ (לענג)) ווייַל מיר אַריבער די וואָג מענגע קלאָץ (לענגטה) מאל. דאָ n און לענג זענען די נומער פון פּאַקיץ און די גרייס פון דער זוכן מעהאַלעך.

אָרט קאַמפּלעקסיטי

די פּלאַץ קאַמפּלעקסיטי פון די אויבן קאָד איז אָ (1) ווייַל מיר נוצן בלויז אַ בייַטעוודיק צו קראָם דעם ענטפער.

רעפֿערענצן