資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中最多可透過k次更新使相等的元素數量最大化
給定任務是在對陣列元素最多進行k次遞增後，找到可以使相等的元素數量最大化的元素個數。
讓我們透過一個例子來理解我們需要做什麼：
輸入
a[] = {1, 3, 8}, k = 4輸出
2
解釋
我們可以透過將1遞增三次，將3遞增四次得到兩個4，使得a[] = {4, 4, 8}。
輸入
arr = {2, 5, 9}, k = 2輸出
0
下面程式中使用的演算法如下：
在main()函式中，初始化int **a[]**，**size**和**k**分別用於儲存陣列元素、陣列大小和最大允許更新次數。
在max()函式中，首先將陣列按升序排序，然後宣告另外兩個陣列int **p[size + 1]** 和 **m[size + 1]**，分別用於儲存字首和和最大值。
迴圈從i = 0到i<= size，初始化p[i] = 0和m[i] = 0。
在迴圈外，設定m[0] = arr[0]和p[0] = arr[0]。
迴圈從i = 1到i<size，設定p[i] = p[i - 1] + arr[i]來計算字首和，設定m[i] = max(m[i - 1], arr[i])來計算到該位置為止的最大值。
迴圈結束後，初始化int Lt = 1, Rt = size, result分別用於儲存左值、右值和最終答案。之後開始二分查詢。
使用條件(Lt < Rt)啟動while迴圈。在迴圈內設定int mid = (Lt + Rt) / 2。檢查是否(EleCal(p, m, mid - 1, k, size))。如果是，則設定result = mid和Lt = mid +1。
否則，只需設定Rt = mid -1。
迴圈結束後，列印result。
在函式bool EleCal()中，使用條件for (int i = 0, j = x; j <= size; j++, i++)啟動for迴圈。
在迴圈內檢查是否(x * m[j] - (p[j] - p[i]) <= k)。如果是，則返回true。迴圈結束後返回false。
示例
#include <bits/stdc++.h>
using namespace std;
bool EleCal(int p[], int m[], int x, int k, int size){
for (int i = 0, j = x; j <= size; j++, i++){
if (x * m[j] - (p[j] - p[i]) <= k)
return true;
}
return false;
}
void Max(int arr[], int size, int k){
// sorting array in ascending order
sort(arr, arr + size);
int p[size + 1];
//array for maximum value
int m[size + 1];
// Initialize prefix array and maximum array
for (int i = 0; i <= size; ++i){
p[i] = 0;
m[i] = 0;
}
m[0] = arr[0];
p[0] = arr[0];
for (int i = 1; i < size; i++){
// Calculating prefix sum of the array
p[i] = p[i - 1] + arr[i];
// Calculating max value upto that position
// in the array
m[i] = max(m[i - 1], arr[i]);
}
// Binary seach
int Lt = 1, Rt = size, result;
while (Lt < Rt){
int mid = (Lt + Rt) / 2;
if (EleCal(p, m, mid - 1, k, size)){
result = mid;
Lt = mid + 1;
}
else
Rt = mid - 1;
}
//answer
cout<<result;
}
// main function
int main(){
int a[] = { 1, 3, 8 };
int size = sizeof(a) / sizeof(a[0]);
int k = 4;
Max(a, size, k);
return 0;
}輸出
2
274 次瀏覽
