数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学在 C++ 中查找修改后数组的最小值可能的最大值
在这个问题中，我们给定一个大小为 n 的数组 arr[] 和一个数字 S。我们的任务是 *查找修改后数组的最小值可能的最大值*。
以下是修改数组的规则：
修改前后数组元素的和的差值应为 S。
修改后的数组中不允许出现负值。
如果修改了数组，则需要最大化数组的最小值。
可以通过 *增加或减少数组的任何元素* 来修改数组。
使用这些约束条件，我们需要找到新的数组并返回数组最小元素的最大值。
让我们举个例子来理解这个问题：
Input : arr[] = {4, 5, 6} S = 2
Output : 4解释
修改后的数组为 {4, 5, 5}
解决方案方法
我们需要最大化修改后数组的最小值。我们将使用二分查找来找到最小值的最佳值，该值介于 *0（最小可能值）* 和 *arrmin*（最大可能值）之间。我们将检查最小可能值的差值。
一些特殊情况：
如果 S 大于数组总和，则不可能有解。
如果 S 等于数组总和，则最小元素的值为 0。
示例
程序说明了我们解决方案的工作原理
#include <iostream>
using namespace std;
int findmaximisedMin(int a[], int n, int S){
int minVal = a[0];
int arrSum = a[0];
for (int i = 1; i < n; i++) {
arrSum += a[i];
minVal = min(a[i], minVal);
}
if (arrSum < S)
return -1;
if (arrSum == S)
return 0;
int s = 0;
int e = minVal;
int ans;
while (s <= e) {
int mid = (s + e) / 2;
if (arrSum - (mid * n) >= S) {
ans = mid;
s = mid + 1;
}
else
e = mid - 1;
}
return ans;
}
int main(){
int a[] = { 4, 5, 6 };
int S = 2;
int n = sizeof(a) / sizeof(a[0]);
cout<<"The maximum value of minimum element of the modified array is "<<findmaximisedMin(a, n, S);
return 0;
}输出
The maximum value of minimum element of the modified array is 4
更新于：2022年1月24日
361 次查看
广告