解 题 报 告
1 1022 Poor contestant Prob原题中文大意;
对于大约十万条数据：如果共奇数条数据则找到最中间那条记录。如果有偶数条记录则忽略。
2 算法思想及解题用到的主要数据结构;
因为数据的规模比较大。如果给十万条记录排序的话显然会超时。考虑到题目只需要找到最中间那条。易想到把数据平分成两部分，第一部分的数据全部大于第二部分的数据。创建两个堆结构。第一部分的较大数据建大小顶堆，第二部分的较小数据建成大顶堆。在插入数据的过程中，动态维护这两个堆，使小顶堆的元素数等于大顶堆的元素数或者小顶堆的元素比大顶堆的元素多一。本题用性线表来存储堆。
3 详细解题思路;
因为最终需要输出一个字符串。为了节省拷贝字符串的开销，把字符串存到一个字符串池中，而每个堆中的元素只维护这个字符串池的索引号。
初始时，小顶堆和大顶堆的大小都是0。
1. 当输入第一条数据时，把这条数据放入小顶堆中。
2. 当输入更多数据时：
2.1 如果小顶堆和大顶堆的元素个数一样多。为保证添加新数据后，我们需要的最中间的数据在小顶堆的上部。又分两种情况处理：
2.1.1 如果待加入数据大于或等于大顶堆的堆顶元素。则把这个待加入数据加入小顶堆。调整小顶堆.
2.1.2 如果待加入数据小于大顶堆的堆顶元素.则把大顶堆的堆顶元素弹出添加到小顶堆，调整这两个堆。之后，把待加入数据加入大顶堆。
2.2 如果小顶堆和大顶堆的元素个数不一样多。因为前面的约定，那么必定是小顶堆的元素个数比大顶堆的元素个数多一个。仍然分两种情况：
2.2.1 如果待加入数据大于小顶堆的堆顶元素。则把待加入数据加入小顶堆并调整，调整后把小顶堆的堆顶弹出加入大顶堆并调整。小顶堆在弹出堆顶元素后再调整一次。
2.2.1 如果待加入数据不大于小顶堆的堆顶元素。则把该数据加入大顶堆，调整大顶堆。
输入结束时直接取小顶堆的堆顶元素即要求的解。根据元素中的字符串索引可以拿到需要打印的字符串，本题中即那位poor contestant。
4 逐步求精算法描述（含过程及变量说明）;
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;
}
//////// 上面的代码在中山大学ACM网站 www.soj.me 上通过.目前的成绩是第14名.
Rank 14 2011-12-07 10:00:19 0.18 sec 2160 KB 6971 Bytes C++ zausiu
注意上面的代码绝不能用C++的标准IO cin cout 做输入输出.如果用C++的IO流会造成超时。我为了调这个超时问题调了整整一天！死活想不到是因为C++ IO的问题.童鞋，一定要用 scanf 和 printf 啊。面对十万级的IO，尤其是在做ACM题，cin cout 是魔鬼。
原因是：
More should be noted about I/O operations in C++. Due to their complex underlying implementation models, cin and cout are comparatively slower than scanf and printf. The difference in performance is shown by many experiences to be more significant if the program is compiled by G++. Therefore if a problem has huge input, using cin and cout will possibly lead to Time Limit Exceed.
6 测试数据;
用一个简单的BASH脚本来创建测试用例。
#! /bin/bash
INDEX=1
SHRESHOLD=100000 // 建十万条数据.
while [ $INDEX -lt $SHRESHOLD ]
do
echo "ADD name$INDEX $RANDOM"
let "INDEX=$INDEX+1"
done
7 对时间复杂度，空间复杂度方面的分析.
时间复杂度是O(log n), 空间复杂度是 O(n).
附原题：
1022. Poor contestant Prob
Description
As everybody known, “BG meeting” is very very popular in the ACM training team of ZSU.
After each online contest, they will go out for “smoking”. Who will be the poor ones that have to BG the others? Of course, the half who solve less problems.
The rule runs well when the number of the contestants is even. But if the number is odd, it is impossible to divide them into two equal parts. It gives a dilemma to the BG meeting committee. After a careful discussion with Mr. Guo, a new rule emerged: if the number of the contestant is odd, the committee will first sort the contestants according to the number of problems they solved, and then they will pick out the middle one. This poor boy or girl will have no chance to attend the BG meeting.
Strange rule, isn`t it?
As the number of the contestants is becoming more and more large, the committee need to write a program which will pick out the poor one efficiently.
Note that: Every contestant solves different number of problems. The total number of the contestants will not exceed 10^5.
Input
There are several cases in the input. The first line of the input will be an integer M, the number of the cases.
Each case is consisted of a list of commands. There are 3 types of commands.
1. Add xxx n : add a record to the data base, where xxx is the name of the contestant, which is only consisted of at most 10 letters or digits, n is the number of problems he/she solved. (Each name will appear in Add commands only once).
2.Query :
3.End :End of the case.
Output
1.For the Query command: If the current number of contestants is odd, the program should output the poor contestant’s name currently even if there is only one contestants, otherwise, just out put “No one!” (without quotes).
2.For the End command:
If the total number of contestants in the data base is even, you should out put “Happy BG meeting!!”(without quotes),otherwise, you should out put the “xxx is so poor. ”(without quotes) where xxx is the name of the poor one.
3.Each case should be separated by a blank line.
Sample Input
2
Add Magicpig 100
Add Radium 600
Add Kingfkong 300
Add Dynamic 700
Query
Add Axing 400
Query
Add Inkfish 1000
Add Carp 800
End
Add Radium 100
Add Magicpig 200
End
Sample Output
No one!
Axing
Radium is so poor.
Happy BG meeting!!
Problem Source
ZSUACM Team Member