資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告