演算法與資料結構實驗題 8.19 分智慧果
題目內容
★實驗任務
老師準備把一筐智慧果分給班上的同學，第i個同學(從1開始編號)分到 \(a_i\) 個智慧果，Bonez (編號為1)是個自私的人，如果他的智慧果數不是班上最多的（即存在某位同學的智慧果數大于他的智慧果數），他會悄悄把別的同學的智慧果放進自己的那堆里，請問他至少需要從其他同學那里拿多少個智慧果，才可以使自己的智慧果數是班上最多的？
★資料輸入
第一行為正整數n; 第二行為n個正整數a[1..n]，\((0 \le a_i \le 10^5)\)
60%的資料 \(1 \le n \le 100\).
100%的資料 \(1 \le n\le 100000\)
★資料輸出
輸出最少需要從別處拿的智慧果數，
輸入示例
3
1 8 0
輸出示例
4
題目分析
\(n_1 : n_i \in U, \forall\ n_1 \ge n_i\) 換句話說, 就是要讓 Bonez 的智慧果數量不少于任何一個同學.
這里我們給出一個例子.
若要讓 Bonez 的智慧果數量最多, 那么遵循貪心的原則, 每一次我們都讓智慧果數量最多的同學給 Bonez 一個智慧果.
這樣看還是不太直觀, 我們不妨按照智慧果數量排個序.
要使得 Bonez 的智慧果最多且操作次數最少, 我們則需要每次從智慧果最多的人那里拿出一個給 Bonez, 并且在該操作之后動態地維護智慧果序列. 直到 Bonez 成為智慧果數量最多的人. 操作的次數就是題目要求的答案.
在這個例子中, 我們不難看出, 演算法的關鍵就是在于怎樣每一次都可以快速的找到序列中最多智慧果的數量. 如何實作呢? 當然是優先佇列.
演算法實作
在這個例子當中, 我們需要高效的知道當前序列中最多的智慧果數量是多少. 而優先佇列正好可以滿足我們的這個要求.
優先佇列可以實作 O(1) 的查找最值. 若算上維護的操作, 那么一次查詢和分配智慧果就是 O(1 + nlog n) = O(nlog n).
對于具體的優先佇列實作這里就不再贅述.
為查找序列中的最大值, 本題使用的是大根堆, 并且以陣列存盤近似滿二叉堆的形式存盤堆.
給出近似滿二叉堆的相關介面, 后續堆的操作有用到.
int _Parent(int x) { return ((x - 1) >> 1); }
int _LChild(int x) { return ((x << 1) + 1); }
int _RChild(int x) { return ((x << 1) + 2); }
題目中主要用到的操作只有兩個分別是: 插入 和 修改
insert()
我們沒辦法直接知道待插入元素在堆中的正確位置, 所以我們要通過這種間接的方式先插入再維護, 從而完成一次堆插入操作.
1/ 插入新元素至堆底
將新插入的元素插入到堆的最底層, 即陣列的最后一個位置, 使其成為一片新的葉子.
2/ 調整元素位置, 保持堆的結構
然后再沿著新插入的這個節點, 向根回溯. 每一次回溯都去判斷當前節點及其兩個子節點是否滿足大根堆的結構.
若否, 則更新堆, 交換不符合的兩個節點的位置, 使得在這個子堆中仍然保持著堆的結構.
不斷回溯, 直到到達堆的根. 完成一次插入操作.
void insert(int n)
{
// 1. 插入新元素至堆底
_heap[_size++] = n;
// 2. 調整元素位置, 保持堆的結構
int buf, scan = _size - 1; // scan 從堆底開始掃描; buf 是 scan 的父節點用來判斷堆結構是否正確
while ((buf = _Parent(scan)) >= 0) // 回圈, 直到 scan 的父節點非零的時候退出
{
if (_heap[scan] < _heap[buf]) // 堆結構已經正確, 退出回圈.
break;
swap(_heap[scan], _heap[buf]); // 交換節點, 使其滿足堆的結構
scan = buf; // 更新 scan, 以繼續向根節點迭代檢查.
}
}
建樹的程序就是不斷地往優先佇列中加入新的元素. 還是用上面提到的例子來演示, 如動圖所示.
solve()
類似于插入操作的設計思想, 要對堆中的元素進行修改, 可以先直接修改, 然后再去維護堆.
1/ 分配智慧果
將堆中最大元素, 即堆頂元素減一, Bonez 的智慧果數量加一. 完成對智慧果數量的修改
2/ 調整元素位置, 保持堆的結構
整體的思想和流程和insert()的基本一致. 不同的是在插入的程序中維護是自底向上的, 而在這次維護的程序中調整是自頂向下的.
具體來說, 先判斷修改后的堆是否還維持著堆的結構.
int solve()
{
int ret = 0; // 記錄分配的次數, 即 Bonez 拿到的智慧果數量
// 重分配智慧果
while (_head < _heap[0]) //回圈, 直到 Bonez 的智慧果數量比堆中的最大元素還大
{
// 1. 進行一次智慧果分配
_heap[0]--; _head++; ret++;
// 2. 調整元素位置, 保持堆的結構
// 自頂向下遍歷檢查
// (這里的 buf 和之前的 buf 不同: buf 是 scan 中更大的子節點的下標)
for (int scan = 0, buf = 1; buf < _size; buf = _LChild(scan))
{
// 找出子節點中更大的那個
if (buf + 1 < _size && _heap[buf] < _heap[buf + 1]) // if (下標不越界 && 另一個子節點更大)
buf++;
if (_heap[scan] > _heap[buf]) // 堆結構已經正確, 退出回圈.
break;
swap(_heap[scan], _heap[buf]); // 交換節點, 使其滿足堆的結構.
scan = buf; // 更新 scan, 以繼續向子節點迭代檢查.
}
print();
}
還是剛才的那個例子. 下面是在優先佇列中的演示.
代碼 codes
#include <iostream>
using namespace std;
class BinaryHeap // 大根堆
{
int *_heap = nullptr; // 存盤堆中的所有元素
int _size = 0; // 堆中元素的數量
int _capacity = 0; // 堆的最大容量
int _head; // Bonez 的智慧果數量
// 用陣列實作近似滿二叉堆的相關介面
int _Parent(int x) { return ((x - 1) >> 1); }
int _LChild(int x) { return ((x << 1) + 1); }
int _RChild(int x) { return ((x << 1) + 2); }
public:
// 初始化
BinaryHeap(int c = 100000) : _capacity(c) { _heap = new int[c + 100]; }
void init(int h) { _head = h; }
void insert(int n)
{
// 1. 插入新元素至堆底
_heap[_size++] = n;
// 2. 調整元素位置, 保持堆的結構
int buf, scan = _size - 1; // scan 從堆底開始掃描; buf 是 scan 的父節點用來判斷堆結構是否正確
while ((buf = _Parent(scan)) >= 0) // 回圈, 直到 scan 的父節點非零的時候退出
{
if (_heap[scan] < _heap[buf]) // 堆結構已經正確, 退出回圈.
break;
swap(_heap[scan], _heap[buf]); // 交換節點, 使其滿足堆的結構
scan = buf; // 更新 scan, 以繼續向根節點迭代檢查.
}
}
int solve()
{
int ret = 0; // 記錄分配的次數, 即 Bonez 拿到的智慧果數量
// 重分配智慧果
while (_head < _heap[0]) //回圈, 直到 Bonez 的智慧果數量比堆中的最大元素還大
{
// 1. 進行一次智慧果分配
_heap[0]--; _head++; ret++;
// 2. 調整元素位置, 保持堆的結構
// 自頂向下遍歷檢查
// (這里的 buf 和之前的 buf 不同: buf 是 scan 中更大的子節點的下標)
for (int scan = 0, buf = 1; buf < _size; buf = _LChild(scan))
{
// 找出子節點中更大的那個
if (buf + 1 < _size && _heap[buf] < _heap[buf + 1]) // if (下標不越界 && 另一個子節點更大)
buf++;
if (_heap[scan] > _heap[buf]) // 堆結構已經正確, 退出回圈.
break;
swap(_heap[scan], _heap[buf]); // 交換節點, 使其滿足堆的結構.
scan = buf; // 更新 scan, 以繼續向子節點迭代檢查.
}
print();
}
return ret;
}
void print()
{
for (int i = 0, j = 1; i < _size; i++)
{
if (i + 1 == j)
{
putchar('\n');
j *= 2;
}
printf("%d ", _heap[i]);
}
cout << endl;
}
};
inline int read();
int main(void)
{
#ifdef LOCAL_COMPILE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int numCount = read();
BinaryHeap heap(numCount);
heap.init(read());
for (int i = 1; i < numCount; i++)
heap.insert(read());
cout << heap.solve();
return 0;
}
inline int read()
{
int ret = 0, sign = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
sign = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
ret = (ret << 1) + (ret << 3) + (ch ^ 48);
ch = getchar();
}
return ret * sign;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/540031.html
標籤：其他