Skip to content

Commit 5e57193

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1760. Minimum Limit of Balls in a Bag
1 parent c7fdcf3 commit 5e57193

File tree

6 files changed

+256
-12
lines changed

6 files changed

+256
-12
lines changed

‎solution/1700-1799/1760.Minimum Limit of Balls in a Bag/README.md

Lines changed: 92 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -13,10 +13,11 @@
1313
<ul>
1414
<li>选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 <strong>正整数</strong> 个球。
1515

16-
<ul>
17-
<li>比方说，一个袋子里有 <code>5</code> 个球，你可以把它们分到两个新袋子里，分别有 <code>1</code> 个和 <code>4</code> 个球，或者分别有 <code>2</code> 个和 <code>3</code> 个球。</li>
18-
</ul>
19-
</li>
16+
<ul>
17+
<li>比方说，一个袋子里有 <code>5</code> 个球，你可以把它们分到两个新袋子里，分别有 <code>1</code> 个和 <code>4</code> 个球，或者分别有 <code>2</code> 个和 <code>3</code> 个球。</li>
18+
</ul>
19+
</li>
20+
2021
</ul>
2122

2223
<p>你的开销是单个袋子里球数目的 <strong>最大值</strong> ，你想要 <strong>最小化</strong> 开销。</p>
@@ -65,27 +66,112 @@
6566
<li><code>1 <= maxOperations, nums[i] <= 10<sup>9</sup></code></li>
6667
</ul>
6768

68-
6969
## 解法
7070

7171
<!-- 这里可写通用的实现逻辑 -->
7272

73+
二分查找。
74+
75+
题目可以转换为：对某个开销值，看它能不能在 maxOperations 次操作内得到。二分枚举开销值，找到最小的开销值即可。
76+
7377
<!-- tabs:start -->
7478

7579
### **Python3**
7680

7781
<!-- 这里可写当前语言的特殊实现逻辑 -->
7882

7983
```python
80-
84+
class Solution:
85+
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
86+
left, right = 1, max(nums)
87+
while left < right:
88+
mid = (left + right) >> 1
89+
ops = sum([(num - 1) // mid for num in nums])
90+
if ops <= maxOperations:
91+
right = mid
92+
else:
93+
left = mid + 1
94+
return left
8195
```
8296

8397
### **Java**
8498

8599
<!-- 这里可写当前语言的特殊实现逻辑 -->
86100

87101
```java
102+
class Solution {
103+
public int minimumSize(int[] nums, int maxOperations) {
104+
int left = 1, right = 1000000000;
105+
while (left < right) {
106+
int mid = (left + right) >>> 1;
107+
long ops = 0;
108+
for (int num : nums) {
109+
ops += (num - 1) / mid;
110+
}
111+
if (ops <= maxOperations) {
112+
right = mid;
113+
} else {
114+
left = mid + 1;
115+
}
116+
}
117+
return left;
118+
}
119+
}
120+
```
121+
122+
### **C++**
123+
124+
```cpp
125+
class Solution {
126+
public:
127+
int minimumSize(vector<int>& nums, int maxOperations) {
128+
int left = 1, right = *max_element(nums.begin(), nums.end());
129+
while (left < right) {
130+
int mid = left + (right - left >> 1);
131+
long long ops = 0;
132+
for (int num : nums) {
133+
ops += (num - 1) / mid;
134+
}
135+
if (ops <= maxOperations) {
136+
right = mid;
137+
} else {
138+
left = mid + 1;
139+
}
140+
}
141+
return left;
142+
}
143+
};
144+
```
88145
146+
### **Go**
147+
148+
```go
149+
func minimumSize(nums []int, maxOperations int) int {
150+
left, right := 1, max(nums)
151+
for left < right {
152+
mid := (left + right) >> 1
153+
var ops int
154+
for _, num := range nums {
155+
ops += (num - 1) / mid
156+
}
157+
if ops <= maxOperations {
158+
right = mid
159+
} else {
160+
left = mid + 1
161+
}
162+
}
163+
return left
164+
}
165+
166+
func max(nums []int) int {
167+
res := 0
168+
for _, num := range nums {
169+
if res < num {
170+
res = num
171+
}
172+
}
173+
return res
174+
}
89175
```
90176

91177
### **...**

‎solution/1700-1799/1760.Minimum Limit of Balls in a Bag/README_EN.md

Lines changed: 90 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -11,10 +11,11 @@
1111
<ul>
1212
<li>Take any bag of balls and divide it into two new bags with a <strong>positive </strong>number of balls.
1313

14-
<ul>
15-
<li>For example, a bag of <code>5</code> balls can become two new bags of <code>1</code> and <code>4</code> balls, or two new bags of <code>2</code> and <code>3</code> balls.</li>
16-
</ul>
17-
</li>
14+
<ul>
15+
<li>For example, a bag of <code>5</code> balls can become two new bags of <code>1</code> and <code>4</code> balls, or two new bags of <code>2</code> and <code>3</code> balls.</li>
16+
</ul>
17+
</li>
18+
1819
</ul>
1920

2021
<p>Your penalty is the <strong>maximum</strong> number of balls in a bag. You want to <strong>minimize</strong> your penalty after the operations.</p>
@@ -61,21 +62,104 @@ The bag with the most number of balls has 2 balls, so your penalty is 2 an you s
6162
<li><code>1 &lt;= maxOperations, nums[i] &lt;= 10<sup>9</sup></code></li>
6263
</ul>
6364

64-
6565
## Solutions
6666

67+
Binary search.
68+
6769
<!-- tabs:start -->
6870

6971
### **Python3**
7072

7173
```python
72-
74+
class Solution:
75+
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
76+
left, right = 1, max(nums)
77+
while left < right:
78+
mid = (left + right) >> 1
79+
ops = sum([(num - 1) // mid for num in nums])
80+
if ops <= maxOperations:
81+
right = mid
82+
else:
83+
left = mid + 1
84+
return left
7385
```
7486

7587
### **Java**
7688

7789
```java
90+
class Solution {
91+
public int minimumSize(int[] nums, int maxOperations) {
92+
int left = 1, right = 1000000000;
93+
while (left < right) {
94+
int mid = (left + right) >>> 1;
95+
long ops = 0;
96+
for (int num : nums) {
97+
ops += (num - 1) / mid;
98+
}
99+
if (ops <= maxOperations) {
100+
right = mid;
101+
} else {
102+
left = mid + 1;
103+
}
104+
}
105+
return left;
106+
}
107+
}
108+
```
109+
110+
### **C++**
111+
112+
```cpp
113+
class Solution {
114+
public:
115+
int minimumSize(vector<int>& nums, int maxOperations) {
116+
int left = 1, right = *max_element(nums.begin(), nums.end());
117+
while (left < right) {
118+
int mid = left + (right - left >> 1);
119+
long long ops = 0;
120+
for (int num : nums) {
121+
ops += (num - 1) / mid;
122+
}
123+
if (ops <= maxOperations) {
124+
right = mid;
125+
} else {
126+
left = mid + 1;
127+
}
128+
}
129+
return left;
130+
}
131+
};
132+
```
78133
134+
### **Go**
135+
136+
```go
137+
func minimumSize(nums []int, maxOperations int) int {
138+
left, right := 1, max(nums)
139+
for left < right {
140+
mid := (left + right) >> 1
141+
var ops int
142+
for _, num := range nums {
143+
ops += (num - 1) / mid
144+
}
145+
if ops <= maxOperations {
146+
right = mid
147+
} else {
148+
left = mid + 1
149+
}
150+
}
151+
return left
152+
}
153+
154+
func max(nums []int) int {
155+
res := 0
156+
for _, num := range nums {
157+
if res < num {
158+
res = num
159+
}
160+
}
161+
return res
162+
}
79163
```
80164

81165
### **...**

‎solution/1700-1799/1760.Minimum Limit of Balls in a Bag/Solution.cpp

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
class Solution {
2+
public:
3+
int minimumSize(vector<int>& nums, int maxOperations) {
4+
int left = 1, right = *max_element(nums.begin(), nums.end());
5+
while (left < right) {
6+
int mid = left + (right - left >> 1);
7+
long long ops = 0;
8+
for (int num : nums) {
9+
ops += (num - 1) / mid;
10+
}
11+
if (ops <= maxOperations) {
12+
right = mid;
13+
} else {
14+
left = mid + 1;
15+
}
16+
}
17+
return left;
18+
}
19+
};

‎solution/1700-1799/1760.Minimum Limit of Balls in a Bag/Solution.go

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
func minimumSize(nums []int, maxOperations int) int {
2+
left, right := 1, max(nums)
3+
for left < right {
4+
mid := (left + right) >> 1
5+
var ops int
6+
for _, num := range nums {
7+
ops += (num - 1) / mid
8+
}
9+
if ops <= maxOperations {
10+
right = mid
11+
} else {
12+
left = mid + 1
13+
}
14+
}
15+
return left
16+
}
17+
18+
func max(nums []int) int {
19+
res := 0
20+
for _, num := range nums {
21+
if res < num {
22+
res = num
23+
}
24+
}
25+
return res
26+
}

‎solution/1700-1799/1760.Minimum Limit of Balls in a Bag/Solution.java

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
class Solution {
2+
public int minimumSize(int[] nums, int maxOperations) {
3+
int left = 1, right = 1000000000;
4+
while (left < right) {
5+
int mid = (left + right) >>> 1;
6+
long ops = 0;
7+
for (int num : nums) {
8+
ops += (num - 1) / mid;
9+
}
10+
if (ops <= maxOperations) {
11+
right = mid;
12+
} else {
13+
left = mid + 1;
14+
}
15+
}
16+
return left;
17+
}
18+
}

‎solution/1700-1799/1760.Minimum Limit of Balls in a Bag/Solution.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
class Solution:
2+
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
3+
left, right = 1, max(nums)
4+
while left < right:
5+
mid = (left + right) >> 1
6+
ops = sum([(num - 1) // mid for num in nums])
7+
if ops <= maxOperations:
8+
right = mid
9+
else:
10+
left = mid + 1
11+
return left

0 commit comments

Comments
 (0)