minimum-time-to-make-array-sum-at-most-x

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two 0-indexed integer arrays <code>nums1</code> and <code>nums2</code> of equal length. Every second, for all indices <code>0 &lt;= i &lt; nums1.length</code>, value of <code>nums1[i]</code> is incremented by <code>nums2[i]</code>. After this is done, you can do the following operation:

<ul>
	<li>Choose an index <code>0 &lt;= i &lt; nums1.length</code> and make <code>nums1[i] = 0</code>.</li>
</ul>

You are also given an integer <code>x</code>.

Return the minimum time in which you can make the sum of all elements of <code>nums1</code> to be less than or equal to <code>x</code>, or <code>-1</code> if this is not possible.

&nbsp;
Example 1:

<pre>
Input: nums1 = [1,2,3], nums2 = [1,2,3], x = 4
Output: 3
Explanation: 
For the 1st second, we apply the operation on i = 0. Therefore nums1 = [0,2+2,3+3] = [0,4,6]. 
For the 2nd second, we apply the operation on i = 1. Therefore nums1 = [0+1,0,6+3] = [1,0,9]. 
For the 3rd second, we apply the operation on i = 2. Therefore nums1 = [1+1,0+2,0] = [2,2,0]. 
Now sum of nums1 = 4. It can be shown that these operations are optimal, so we return 3.

</pre>

Example 2:

<pre>
Input: nums1 = [1,2,3], nums2 = [3,3,3], x = 4
Output: -1
Explanation: It can be shown that the sum of nums1 will always be greater than x, no matter which operations are performed.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums1.length &lt;= 103</code></li>
	<li><code>1 &lt;= nums1[i] &lt;= 103</code></li>
	<li><code>0 &lt;= nums2[i] &lt;= 103</code></li>
	<li><code>nums1.length == nums2.length</code></li>
	<li><code>0 &lt;= x &lt;= 106</code></li>
</ul>

minimumTime

Minimum Time to Make Array Sum At Most x

Array

Dynamic Programming

Sorting

给你两个长度相等下标从 0&nbsp;开始的整数数组&nbsp;<code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;。每一秒，对于所有下标&nbsp;<code>0 &lt;= i &lt; nums1.length</code>&nbsp;，<code>nums1[i]</code>&nbsp;的值都增加&nbsp;<code>nums2[i]</code>&nbsp;。操作&nbsp;完成后&nbsp;，你可以进行如下操作：

<ul>
	<li>选择任一满足&nbsp;<code>0 &lt;= i &lt; nums1.length</code>&nbsp;的下标 <code>i</code>&nbsp;，并使&nbsp;<code>nums1[i] = 0</code>&nbsp;。</li>
</ul>

同时给你一个整数&nbsp;<code>x</code>&nbsp;。

请你返回使&nbsp;<code>nums1</code>&nbsp;中所有元素之和 小于等于&nbsp;<code>x</code>&nbsp;所需要的 最少&nbsp;时间，如果无法实现，那么返回 <code>-1</code>&nbsp;。

&nbsp;

示例 1：

<pre>
输入：nums1 = [1,2,3], nums2 = [1,2,3], x = 4
输出：3
解释：
第 1 秒，我们对 i = 0 进行操作，得到 nums1 = [0,2+2,3+3] = [0,4,6] 。
第 2 秒，我们对 i = 1 进行操作，得到 nums1 = [0+1,0,6+3] = [1,0,9] 。
第 3 秒，我们对 i = 2 进行操作，得到 nums1 = [1+1,0+2,0] = [2,2,0] 。
现在 nums1 的和为 4 。不存在更少次数的操作，所以我们返回 3 。
</pre>

示例 2：

<pre>
输入：nums1 = [1,2,3], nums2 = [3,3,3], x = 4
输出：-1
解释：不管如何操作，nums1 的和总是会超过 x 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums1.length &lt;= 103</code></li>
	<li><code>1 &lt;= nums1[i] &lt;= 103</code></li>
	<li><code>0 &lt;= nums2[i] &lt;= 103</code></li>
	<li><code>nums1.length == nums2.length</code></li>
	<li><code>0 &lt;= x &lt;= 106</code></li>
</ul>