int g_name_pool_index = 0; // 名字池的当前索引号.char g_name_pool[100001][11]; // 用来存名字的字符串池.
下面是堆相关的描述。
struct heap_elem_t
{
// string _name;
int _name_index; // 名字的索引
int _solved_count; // 原题意中表示解决了多少个问题.用这个数量比较堆元素的大小。
};
// STL 用的堆算法的比较算子.
struct heap_elem_less_comparator
{
bool operator()(const heap_elem_t& left, const heap_elem_t& right)
{
return left._solved_count < right._solved_count;
}
};
// STL 用的堆算法的比较算子.
struct heap_elem_larger_comparator
{
bool operator()(const heap_elem_t& left, const heap_elem_t& right)
{
return left._solved_count > right._solved_count;
}
};
heap_elem_less_comparator less_comp;
heap_elem_larger_comparator larger_comp;
// 从下往而上调整堆。用到了STL的堆调整算法。堆元素存在线性表中，但不用第一个元素。因为之前的版本用自己写的堆调整算法为了计算坐标方便就不用第一个元素。
inline void adjust_heap_up(heap_elem_t heap[], int tail_pos, bool inc)
{
if ( inc )
{
push_heap(heap+1, heap+tail_pos+1, larger_comp);
}
else
{
push_heap(heap+1, heap+tail_pos+1, less_comp);
}
}
// 把堆顶元素弹出.并调整余下的元素仍然是一个堆。也用了STL的算法.
inline void popup_the_top(heap_elem_t heap[], int tail_pos, bool inc)
{
if ( inc )
{
pop_heap(heap+1, heap+tail_pos+1, larger_comp);
}
else
{
pop_heap(heap+1, heap+tail_pos+1, less_comp);
}
}
// 下面是自已写的堆调整算法。有从上而下的调整，也有从下而上的调整。
/** 调整堆.从下往下调整.
-
@param heap 堆的首地址.用顺序表存放堆.但不用下标为0的元素.这个元素可用来作临时存储.
-
@param summit_pos 堆顶的位置.summit_pos > 0
-
@param tail_pos 最后一个元素的位置.tail_pos > 0
-
@param inc 是否建小顶堆.如果false则大顶堆.
*/
void adjust_heap_top2bottom(heap_elem_t heap[], int summit_pos, int tail_pos, bool inc)
{
int i;
heap[0] = heap[summit_pos]; // 存下堆顶的元素先.
for ( i = 2 * summit_pos; i <= tail_pos; i *= 2 )
{
if ( inc ) // 调整小顶堆
{
if ( i < tail_pos && heap[i]._solved_count > heap[i+1]._solved_count )
i++;
if ( ! (heap[0]._solved_count > heap[i]._solved_count) )
break;
}
else // 调整大顶堆
{
if ( i < tail_pos && heap[i]._solved_count < heap[i+1]._solved_count )
i++;
if ( ! (heap[0]._solved_count < heap[i]._solved_count) )
break;
}
heap[summit_pos] = heap[i];
summit_pos = i;
}
heap[summit_pos] = heap[0];
}
/** 调整堆.从下往上调整.
-
@param heap 堆的首地址.用顺序表存放堆.但不用下标为0的元素.这个元素可用来作临时存储.
-
@param tail_pos 最后一个元素的位置.tail_pos > 0
-
@param inc 是否建小顶堆.如果false则大顶堆.
*/
void adjust_heap_bottom2top(heap_elem_t heap[], int tail_pos, bool inc)
{
int i;
heap[0] = heap[tail_pos];
for ( i = tail_pos; i > 1; i /= 2 )
{
int parent_pos = i / 2;
if ( inc ) // 调整小顶堆
{
if ( heap[parent_pos]._solved_count > heap[0]._solved_count )
{
heap[i] = heap[parent_pos];
}
else
{
break;
}
}
else // 调整大顶堆
{
if ( heap[parent_pos]._solved_count < heap[0]._solved_count )
{
heap[i] = heap[parent_pos];
}
else
{
break;
}
}
}
heap[i] = heap[0];
}
5 程序注释清单（重要过程的说明）;
// poor_guy.cpp : Defines the entry point for the console application. //
#include <algorithm> #include <string> #include <vector> #include <string.h> #include <stdio.h>
using namespace std;
template<typename T> class my_vector { public: my_vector(T* addr) { m_ary = addr; m_ava_idx = 0; } ~my_vector() { // delete []m_ary; }
T& operator[](int index) { return m_ary[index]; }
void push_back(const T& v) { m_ary[m_ava_idx++] = v; }
void resize(int size) { m_ava_idx = size; }
void shrink(int dec) { m_ava_idx -= dec; }
int size() { return m_ava_idx; } private: T* m_ary; int m_ava_idx; };
// 堆的结点定义 int g_name_pool_index = 0; char g_name_pool[100001][11];
struct heap_elem_t { // string _name; int _name_index; int _solved_count; };
heap_elem_t g_heap_elems0[50002]; heap_elem_t g_heap_elems1[50002];
struct heap_elem_less_comparator { bool operator()(const heap_elem_t& left, const heap_elem_t& right) { return left._solved_count < right._solved_count; } };
struct heap_elem_larger_comparator { bool operator()(const heap_elem_t& left, const heap_elem_t& right) { return left._solved_count > right._solved_count; } };
heap_elem_less_comparator less_comp; heap_elem_larger_comparator larger_comp;
// / inc 为真时调整为小顶堆，为false时调整为大顶堆。 / // inline void adjust_heap_up(heap_elem_t heap[], int tail_pos, bool inc) { if ( inc ) { push_heap(heap+1, heap+tail_pos+1, larger_comp); } else { push_heap(heap+1, heap+tail_pos+1, less_comp); } }
inline void popup_the_top(heap_elem_t heap[], int tail_pos, bool inc) { if ( inc ) { pop_heap(heap+1, heap+tail_pos+1, larger_comp); } else { pop_heap(heap+1, heap+tail_pos+1, less_comp); } }
int main(int argc, char* argv[]) { const int BUFF_LEN = 64; char buff[BUFF_LEN]; int case_count; // 记有多少个case; int contestant_count; my_vector<heap_elem_t> littletop_heap(g_heap_elems0); my_vector<heap_elem_t> bigtop_heap(g_heap_elems1); heap_elem_t contestant; string name; // vector<string> output_vec;
scanf("%d", &case_count); for ( int i = 0; i < case_count; i++ ) { littletop_heap.resize(1); // 为了方便计算.下标0的位置不存堆的元素. bigtop_heap.resize(1); g_name_pool_index = 0; contestant_count = 0;
while(true) { scanf("%s", buff);
int little_heap_count = littletop_heap.size() - 1; int big_heap_count = bigtop_heap.size() - 1;
if ( buff[0] == 'Q' ) // 查询. Querry { if ( little_heap_count == big_heap_count || 0 == contestant_count ) { printf(“No one!\n”); //output_vec.push_back(“No one!\n”); } else { printf("%s\n", g_name_pool[littletop_heap[1]._name_index]); //output_vec.push_back(g_name_pool[littletop_heap[1]._name_index]); //output_vec.push_back("\n"); } } else if ( buff[0] == 'E' ) // 结束. { if ( little_heap_count == big_heap_count || 0 == contestant_count ) { printf(“Happy BG meeting!!\n”); //output_vec.push_back(“Happy BG meeting!!\n”); } else { printf("%s%s",g_name_pool[littletop_heap[1]._name_index], " is so poor.\n"); //output_vec.push_back(g_name_pool[littletop_heap[1]._name_index]); //output_vec.push_back(" is so poor.\n"); }
break; } else if( buff[0] == 'A' )// 加入参赛者数据. { contestant_count ++;
scanf("%s", g_name_pool[g_name_pool_index]); contestant._name_index = g_name_pool_index; g_name_pool_index++; scanf("%d", &contestant._solved_count);
if ( 1 == contestant_count ) // 第一个参赛者数据. { littletop_heap.push_back(contestant); } else if ( little_heap_count == big_heap_count ) // 两个堆的元素相等. { // 新元素大于大顶堆的堆顶元素，所以插入小顶堆. if ( contestant._solved_count >= bigtop_heap[1]._solved_count ) { littletop_heap.push_back(contestant); adjust_heap_up(&littletop_heap[0], littletop_heap.size()-1, true); } else { heap_elem_t top = bigtop_heap[1]; popup_the_top(&bigtop_heap[0], bigtop_heap.size()-1, false); bigtop_heap.shrink(1);
bigtop_heap.push_back(contestant); adjust_heap_up(&bigtop_heap[0], bigtop_heap.size()-1, false);
littletop_heap.push_back(top); adjust_heap_up(&littletop_heap[0], littletop_heap.size()-1, true); } } else // 不等.只可能是小顶堆比大顶堆多1. { if ( contestant._solved_count > littletop_heap[1]._solved_count ) { littletop_heap.push_back(contestant); adjust_heap_up(&littletop_heap[0], littletop_heap.size()-1, true);
heap_elem_t top = littletop_heap[1]; popup_the_top(&littletop_heap[0], littletop_heap.size()-1, true); littletop_heap.shrink(1);
bigtop_heap.push_back(top); adjust_heap_up(&bigtop_heap[0], bigtop_heap.size()-1, false); } else { bigtop_heap.push_back(contestant); adjust_heap_up(&bigtop_heap[0], bigtop_heap.size()-1, false); } } } }
if ( i + 1 < case_count ) { printf("\n"); //output_vec.push_back("\n"); } }
//for ( int i = 0; i < output_vec.size(); i++ ) //{ // cout << output_vec[i]; //}
return 0; }
#! /bin/bashINDEX=1
SHRESHOLD=100000 // 建十万条数据.
while [ $INDEX -lt $SHRESHOLD ]
do
echo “ADD name$INDEX $RANDOM”
let “INDEX=$INDEX+1”
done