Иқтидори фиристодани бастаҳо дар давоми D рӯзи ҳалли Leetcode


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon
тартиботи ҳарбӣ Ҷустуҷӯи бинарӣ

Изҳороти мушкилот

Дар масъалаи "Иқтидори фиристодани бастаҳо дар тӯли D рӯз", мо бастаҳоеро дар бандари А дорем, ки бояд дар тӯли D рӯз ба бандари B интиқол дода шаванд.

ба мо массиви вазнҳо дода мешавад, ки вазни ҳар як баста ва миқдори рӯзҳои интиқоли бастаҳоро дар бар мегирад. Вазифаи мо иборат аз он аст, ки зарфияти ҳадди аққали борбардории киштиро, ки барои интиқоли бастаҳо аз бандари А ба бандари B дар давоми рӯзи D истифода мешавад.

ҳалли leetcode ба иқтидори фиристодани бастаҳо дар давоми D рӯз

мисол

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 рӯз интиқол диҳанд.

Усули қобилияти фиристодани бастаҳо дар давоми D рӯзи ҳалли Leetcode

Аввалин ва муҳимтарин чиз барои ҳалли ин мушкил овардани мушоҳидаҳост. Инҳоянд чанд мушоҳидаҳо барои фосилаи ҷустуҷӯи мо:

  1. Иқтидори борбардории киштӣ бояд ҳадди аққал ба бастае баробар бошад, ки вазни ҳадди аксараш ҳадди аксар (вазнҳо) бошад. биёед онро ҳамчун номгузорӣ кунем Оғоз.
  2. Мо метавонем зарфияти максималии киштиро ба маблағи вазни ҳамаи бастаҳое, ки ҷамъ (вазнҳо) мебошанд, маҳдуд кунем. биёед онро ҳамчун номгузорӣ кунем Поён.

Ҳоло мо фосилаи ҷустуҷӯро дорем. Фарз мекунем, ки андозаи фосила чунин аст дарозӣ ва шумораи бастаҳо ин аст n.  Равиши соддалавҳона метавонад тафтиш кардани ҳар як арзиши фосила бошад, агар он миқдори борбардорӣ метавонад бастаҳоро дар муддати D рӯз бомуваффақият интиқол диҳад ва аз онҳо ҳадди ақалро интихоб кунад. Мураккабии вақт барои муносибати соддалавҳона Length * n хоҳад буд.

Мо метавонем мураккабии вақтро бо истифода аз Ҷустуҷӯи бинарӣ ба ҷои Ҷустуҷӯи Хатӣ беҳтар намоем.

Мураккабии вақт бо истифодаи Ҷустуҷӯи бинарӣ равиш log (Length) * n хоҳад буд.

татбиќи

Рамзи C ++ барои иқтидори фиристодани бастаҳо дар давоми D рӯзи Leetcode Solution

#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 барои иқтидори фиристодани бастаҳо дар давоми D рӯзи Leetcode Solution

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

Таҳлили мураккабии қобилияти фиристодани бастаҳо дар давоми D рӯзи ҳалли Leetcode

Мураккабии вақт

Мураккабии вақти рамзи боло дар он аст O (n * log (Дарозӣ)) зеро мо журнали (Length) массиви вазнҳоро тай карда истодаем. Дар инҷо n ва Length рақами бастаҳо ва андозаи фосилаи ҷустуҷӯ мебошанд.

Мураккабии фазо

Мураккабии фазоии рамзи дар боло зикршуда О (1) зеро мо барои нигоҳ доштани ҷавоб танҳо як тағирёбандаро истифода мебарем.

Адабиёт