使得位置 i 處的元素包含在 a[i] 個對中的對的最大數量

---

在本文中，我們將找到索引對的數量，使得索引 i 最多可以包含在 a[i] 個對中。

在本文中討論的方法中，我們將使用一個優先佇列資料結構，它將包含陣列的元素。優先佇列資料結構將是一個最大堆，它允許我們在 log(N) 時間內獲取陣列的當前最大元素。它還允許我們在相同的時間內修改元素並將其重新插入。我們將從優先佇列中取出最大的兩個元素，用這兩個元素的索引組成一對，減少這兩個元素，然後將其重新插入。如果我們一直這樣做，直到優先佇列只剩下一個元素，我們將得到所需的結果。

問題陳述

給定一個大小為 N 的包含整數元素的陣列，我們需要找到我們可以建立的對的最大數量，使得索引 i 處的元素最多隻能包含在 a[i] 個對中。

示例

輸入

arr = {1,2,3,4}

輸出

5

解釋

可以建立以下索引對：

{1,2}, {2,4}, {3,4}, {3,4}, {3,4}

所以，輸出為 5。

輸入

arr = {0,0,1,1,1}

輸出

1

解釋

只能透過取索引 3、4 和 5 中的任意兩個來建立單個對。

因此，輸出為 1。

輸入

arr = {1,3,2,0,6}

輸出

6

解釋

我們可以使用以下索引建立對：

{1,5}, {2,5}, {2,5}, {2,5}, {3,5}, {3,5}

所以，輸出為 6。

方法 1

在這種方法中，我們將使用一種利用優先佇列資料結構的方法。此資料結構將儲存陣列元素，並將實現為最大堆。這種結構的選擇使我們能夠在對數時間 (O(log N)) 內有效地從陣列中檢索當前最大元素。此外，它還能在相同的時間範圍內方便地修改元素並重新插入。該過程包括從優先佇列中提取前兩個最大元素，為這些元素生成索引對，減少其值，將結果加 1，然後將其放回佇列中。透過迭代執行這些步驟，直到優先佇列中只剩下一個元素，我們可以達到預期的結果。

演算法

• 步驟 1 - 初始化一個優先佇列資料結構

• 步驟 2 - 遍歷所有陣列元素，如果元素大於 0，則將其推入優先佇列。

• 步驟 3 - 初始化一個 while 迴圈，該迴圈將一直執行到優先佇列至少有兩個元素。

• 步驟 3.1 - 同時，用 0 初始化一個結果變數。

• 步驟 4 - 在 while 迴圈中，從優先佇列中彈出前兩個元素，即陣列的當前最大元素。

• 步驟 4.1 - 用這兩個元素的索引組成一對，並將每個元素的值減少 1。

• 步驟 4.2 - 如果減少操作後一個或兩個元素的值仍然大於零，則將其放回優先佇列。

• 步驟 4.3 - 將結果值增加 1。

• 步驟 5 - while 迴圈結束後，返回結果。

示例

#include <bits/stdc++.h> 
using namespace std; 
int Max_pair_count(vector<int> &arr){ 
   priority_queue<int> elements;
   int res = 0;
   for(int i=0;i<arr.size();i++){
      if(arr[i]>0)
         elements.push(arr[i]);
   }
   while(elements.size()>1){
      int x = elements.top();
      elements.pop();
      int y = elements.top();
      elements.pop();
      x--;
      y--;
      res++;
      if(x>0)elements.push(x);
      if(y>0)elements.push(y);
   }
   return res;
} 
int main(){ 
   vector<int> arr = {1,3,2,0,6};
   cout<<Max_pair_count(arr)<<endl; 
   return 0; 
}

輸出

6

時間複雜度 - O(M*log(M))，其中 M 是陣列中所有元素的總和。

空間複雜度 - O(N)，其中 N 是陣列中元素的數量