{"id":256,"date":"2011-12-05T21:27:27","date_gmt":"2011-12-05T13:27:27","guid":{"rendered":"http:\/\/ykyi.net\/?p=256"},"modified":"2011-12-05T21:27:27","modified_gmt":"2011-12-05T13:27:27","slug":"sicily-1022-poor-contestant-prob-%e8%a7%a3%e9%a2%98%e6%8a%a5%e5%91%8a%e3%80%82","status":"publish","type":"post","link":"https:\/\/ykyi.net\/?p=256","title":{"rendered":"sicily 1022 Poor contestant Prob \u89e3\u9898\u62a5\u544a\u3002"},"content":{"rendered":"<div>\n<p>&nbsp;<\/p>\n<div>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;\u89e3 &nbsp;\u9898 &nbsp;\u62a5 &nbsp;\u544a<\/div>\n<div>&nbsp;<\/div>\n<div>1 1022 Poor contestant Prob\u539f\u9898\u4e2d\u6587\u5927\u610f;<\/div>\n<div>&nbsp;<\/div>\n<div>\u5bf9\u4e8e\u5927\u7ea6\u5341\u4e07\u6761\u6570\u636e\uff1a\u5982\u679c\u5171\u5947\u6570\u6761\u6570\u636e\u5219\u627e\u5230\u6700\u4e2d\u95f4\u90a3\u6761\u8bb0\u5f55\u3002\u5982\u679c\u6709\u5076\u6570\u6761\u8bb0\u5f55\u5219\u5ffd\u7565\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>2 \u7b97\u6cd5\u601d\u60f3\u53ca\u89e3\u9898\u7528\u5230\u7684\u4e3b\u8981\u6570\u636e\u7ed3\u6784;<\/div>\n<div>&nbsp;<\/div>\n<div>\u56e0\u4e3a\u6570\u636e\u7684\u89c4\u6a21\u6bd4\u8f83\u5927\u3002\u5982\u679c\u7ed9\u5341\u4e07\u6761\u8bb0\u5f55\u6392\u5e8f\u7684\u8bdd\u663e\u7136\u4f1a\u8d85\u65f6\u3002\u8003\u8651\u5230\u9898\u76ee\u53ea\u9700\u8981\u627e\u5230\u6700\u4e2d\u95f4\u90a3\u6761\u3002\u6613\u60f3\u5230\u628a\u6570\u636e\u5e73\u5206\u6210\u4e24\u90e8\u5206\uff0c\u7b2c\u4e00\u90e8\u5206\u7684\u6570\u636e\u5168\u90e8\u5927\u4e8e\u7b2c\u4e8c\u90e8\u5206\u7684\u6570\u636e\u3002\u521b\u5efa\u4e24\u4e2a\u5806\u7ed3\u6784\u3002\u7b2c\u4e00\u90e8\u5206\u7684\u8f83\u5927\u6570\u636e\u5efa\u5927\u5c0f\u9876\u5806\uff0c\u7b2c\u4e8c\u90e8\u5206\u7684\u8f83\u5c0f\u6570\u636e\u5efa\u6210\u5927\u9876\u5806\u3002\u5728\u63d2\u5165\u6570\u636e\u7684\u8fc7\u7a0b\u4e2d\uff0c\u52a8\u6001\u7ef4\u62a4\u8fd9\u4e24\u4e2a\u5806\uff0c\u4f7f\u5c0f\u9876\u5806\u7684\u5143\u7d20\u6570\u7b49\u4e8e\u5927\u9876\u5806\u7684\u5143\u7d20\u6570\u6216\u8005\u5c0f\u9876\u5806\u7684\u5143\u7d20\u6bd4\u5927\u9876\u5806\u7684\u5143\u7d20\u591a\u4e00\u3002\u672c\u9898\u7528\u6027\u7ebf\u8868\u6765\u5b58\u50a8\u5806\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>3 \u8be6\u7ec6\u89e3\u9898\u601d\u8def;<\/div>\n<div>&nbsp;<\/div>\n<div>\u56e0\u4e3a\u6700\u7ec8\u9700\u8981\u8f93\u51fa\u4e00\u4e2a\u5b57\u7b26\u4e32\u3002\u4e3a\u4e86\u8282\u7701\u62f7\u8d1d\u5b57\u7b26\u4e32\u7684\u5f00\u9500\uff0c\u628a\u5b57\u7b26\u4e32\u5b58\u5230\u4e00\u4e2a\u5b57\u7b26\u4e32\u6c60\u4e2d\uff0c\u800c\u6bcf\u4e2a\u5806\u4e2d\u7684\u5143\u7d20\u53ea\u7ef4\u62a4\u8fd9\u4e2a\u5b57\u7b26\u4e32\u6c60\u7684\u7d22\u5f15\u53f7\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>\u521d\u59cb\u65f6\uff0c\u5c0f\u9876\u5806\u548c\u5927\u9876\u5806\u7684\u5927\u5c0f\u90fd\u662f0\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>1. \u5f53\u8f93\u5165\u7b2c\u4e00\u6761\u6570\u636e\u65f6\uff0c\u628a\u8fd9\u6761\u6570\u636e\u653e\u5165\u5c0f\u9876\u5806\u4e2d\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>2. \u5f53\u8f93\u5165\u66f4\u591a\u6570\u636e\u65f6\uff1a<\/div>\n<div>&nbsp;<\/div>\n<div>2.1 \u5982\u679c\u5c0f\u9876\u5806\u548c\u5927\u9876\u5806\u7684\u5143\u7d20\u4e2a\u6570\u4e00\u6837\u591a\u3002\u4e3a\u4fdd\u8bc1\u6dfb\u52a0\u65b0\u6570\u636e\u540e\uff0c\u6211\u4eec\u9700\u8981\u7684\u6700\u4e2d\u95f4\u7684\u6570\u636e\u5728\u5c0f\u9876\u5806\u7684\u4e0a\u90e8\u3002\u53c8\u5206\u4e24\u79cd\u60c5\u51b5\u5904\u7406\uff1a<\/div>\n<div>&nbsp;<\/div>\n<div>2.1.1 \u5982\u679c\u5f85\u52a0\u5165\u6570\u636e\u5927\u4e8e\u6216\u7b49\u4e8e\u5927\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u3002\u5219\u628a\u8fd9\u4e2a\u5f85\u52a0\u5165\u6570\u636e\u52a0\u5165\u5c0f\u9876\u5806\u3002\u8c03\u6574\u5c0f\u9876\u5806.<\/div>\n<div>&nbsp;<\/div>\n<div>2.1.2 \u5982\u679c\u5f85\u52a0\u5165\u6570\u636e\u5c0f\u4e8e\u5927\u9876\u5806\u7684\u5806\u9876\u5143\u7d20.\u5219\u628a\u5927\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u5f39\u51fa\u6dfb\u52a0\u5230\u5c0f\u9876\u5806\uff0c\u8c03\u6574\u8fd9\u4e24\u4e2a\u5806\u3002\u4e4b\u540e\uff0c\u628a\u5f85\u52a0\u5165\u6570\u636e\u52a0\u5165\u5927\u9876\u5806\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>2.2 \u5982\u679c\u5c0f\u9876\u5806\u548c\u5927\u9876\u5806\u7684\u5143\u7d20\u4e2a\u6570\u4e0d\u4e00\u6837\u591a\u3002\u56e0\u4e3a\u524d\u9762\u7684\u7ea6\u5b9a\uff0c\u90a3\u4e48\u5fc5\u5b9a\u662f\u5c0f\u9876\u5806\u7684\u5143\u7d20\u4e2a\u6570\u6bd4\u5927\u9876\u5806\u7684\u5143\u7d20\u4e2a\u6570\u591a\u4e00\u4e2a\u3002\u4ecd\u7136\u5206\u4e24\u79cd\u60c5\u51b5\uff1a<\/div>\n<div>&nbsp;<\/div>\n<div>2.2.1 \u5982\u679c\u5f85\u52a0\u5165\u6570\u636e\u5927\u4e8e\u5c0f\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u3002\u5219\u628a\u5f85\u52a0\u5165\u6570\u636e\u52a0\u5165\u5c0f\u9876\u5806\u5e76\u8c03\u6574\uff0c\u8c03\u6574\u540e\u628a\u5c0f\u9876\u5806\u7684\u5806\u9876\u5f39\u51fa\u52a0\u5165\u5927\u9876\u5806\u5e76\u8c03\u6574\u3002\u5c0f\u9876\u5806\u5728\u5f39\u51fa\u5806\u9876\u5143\u7d20\u540e\u518d\u8c03\u6574\u4e00\u6b21\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>2.2.1 \u5982\u679c\u5f85\u52a0\u5165\u6570\u636e\u4e0d\u5927\u4e8e\u5c0f\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u3002\u5219\u628a\u8be5\u6570\u636e\u52a0\u5165\u5927\u9876\u5806\uff0c\u8c03\u6574\u5927\u9876\u5806\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>\u8f93\u5165\u7ed3\u675f\u65f6\u76f4\u63a5\u53d6\u5c0f\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u5373\u8981\u6c42\u7684\u89e3\u3002\u6839\u636e\u5143\u7d20\u4e2d\u7684\u5b57\u7b26\u4e32\u7d22\u5f15\u53ef\u4ee5\u62ff\u5230\u9700\u8981\u6253\u5370\u7684\u5b57\u7b26\u4e32\uff0c\u672c\u9898\u4e2d\u5373\u90a3\u4f4dpoor contestant\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>4 \u9010\u6b65\u6c42\u7cbe\u7b97\u6cd5\u63cf\u8ff0\uff08\u542b\u8fc7\u7a0b\u53ca\u53d8\u91cf\u8bf4\u660e\uff09;<\/div>\n<div>\n<pre class=\"brush:cpp\">int g_name_pool_index = 0;   \/\/ \u540d\u5b57\u6c60\u7684\u5f53\u524d\u7d22\u5f15\u53f7.\n\nchar g_name_pool[100001][11];  \/\/ \u7528\u6765\u5b58\u540d\u5b57\u7684\u5b57\u7b26\u4e32\u6c60.\n\n\n\n\u4e0b\u9762\u662f\u5806\u76f8\u5173\u7684\u63cf\u8ff0\u3002\n\nstruct heap_elem_t\n\n{\n\n\/\/ string _name;\n\nint _name_index;  \/\/ \u540d\u5b57\u7684\u7d22\u5f15\n\nint _solved_count;  \/\/ \u539f\u9898\u610f\u4e2d\u8868\u793a\u89e3\u51b3\u4e86\u591a\u5c11\u4e2a\u95ee\u9898.\u7528\u8fd9\u4e2a\u6570\u91cf\u6bd4\u8f83\u5806\u5143\u7d20\u7684\u5927\u5c0f\u3002\n\n};\n\n\/\/ STL \u7528\u7684\u5806\u7b97\u6cd5\u7684\u6bd4\u8f83\u7b97\u5b50.\n\nstruct heap_elem_less_comparator\n\n{\n\nbool operator()(const heap_elem_t&amp; left,  const heap_elem_t&amp; right)\n\n{\n\nreturn left._solved_count &lt; right._solved_count;\n\n}\n\n};\n\n\n\n\/\/ STL \u7528\u7684\u5806\u7b97\u6cd5\u7684\u6bd4\u8f83\u7b97\u5b50.\n\nstruct heap_elem_larger_comparator\n\n{\n\nbool operator()(const heap_elem_t&amp; left,  const heap_elem_t&amp; right)\n\n{\n\nreturn left._solved_count &gt; right._solved_count;\n\n}\n\n};\n\nheap_elem_less_comparator less_comp;\n\nheap_elem_larger_comparator larger_comp;\n\n\/\/ \u4ece\u4e0b\u5f80\u800c\u4e0a\u8c03\u6574\u5806\u3002\u7528\u5230\u4e86STL\u7684\u5806\u8c03\u6574\u7b97\u6cd5\u3002\u5806\u5143\u7d20\u5b58\u5728\u7ebf\u6027\u8868\u4e2d\uff0c\u4f46\u4e0d\u7528\u7b2c\u4e00\u4e2a\u5143\u7d20\u3002\u56e0\u4e3a\u4e4b\u524d\u7684\u7248\u672c\u7528\u81ea\u5df1\u5199\u7684\u5806\u8c03\u6574\u7b97\u6cd5\u4e3a\u4e86\u8ba1\u7b97\u5750\u6807\u65b9\u4fbf\u5c31\u4e0d\u7528\u7b2c\u4e00\u4e2a\u5143\u7d20\u3002\n\ninline void adjust_heap_up(heap_elem_t heap[], int tail_pos, bool inc)\n\n{\n\nif ( inc )\n\n{\n\npush_heap(heap+1, heap+tail_pos+1, larger_comp);\n\n}\n\nelse\n\n{\n\npush_heap(heap+1, heap+tail_pos+1, less_comp);\n\n}\n\n}\n\n\/\/ \u628a\u5806\u9876\u5143\u7d20\u5f39\u51fa.\u5e76\u8c03\u6574\u4f59\u4e0b\u7684\u5143\u7d20\u4ecd\u7136\u662f\u4e00\u4e2a\u5806\u3002\u4e5f\u7528\u4e86STL\u7684\u7b97\u6cd5.\n\ninline void popup_the_top(heap_elem_t heap[], int tail_pos, bool inc)\n\n{\n\nif ( inc )\n\n{\n\npop_heap(heap+1, heap+tail_pos+1, larger_comp);\n\n}\n\nelse\n\n{\n\npop_heap(heap+1, heap+tail_pos+1, less_comp);\n\n}\n\n}\n\n\/\/ \u4e0b\u9762\u662f\u81ea\u5df2\u5199\u7684\u5806\u8c03\u6574\u7b97\u6cd5\u3002\u6709\u4ece\u4e0a\u800c\u4e0b\u7684\u8c03\u6574\uff0c\u4e5f\u6709\u4ece\u4e0b\u800c\u4e0a\u7684\u8c03\u6574\u3002\n\n\/** \u8c03\u6574\u5806.\u4ece\u4e0b\u5f80\u4e0b\u8c03\u6574.\n\n* @param heap \u5806\u7684\u9996\u5730\u5740.\u7528\u987a\u5e8f\u8868\u5b58\u653e\u5806.\u4f46\u4e0d\u7528\u4e0b\u6807\u4e3a0\u7684\u5143\u7d20.\u8fd9\u4e2a\u5143\u7d20\u53ef\u7528\u6765\u4f5c\u4e34\u65f6\u5b58\u50a8.\n\n* @param summit_pos \u5806\u9876\u7684\u4f4d\u7f6e.summit_pos &gt; 0\n\n* @param tail_pos \u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u4f4d\u7f6e.tail_pos &gt; 0\n\n* @param inc \u662f\u5426\u5efa\u5c0f\u9876\u5806.\u5982\u679cfalse\u5219\u5927\u9876\u5806.\n\n*\/\n\nvoid adjust_heap_top2bottom(heap_elem_t heap[], int summit_pos, int tail_pos, bool inc)\n\n{\n\nint i;\n\nheap[0] = heap[summit_pos];  \/\/ \u5b58\u4e0b\u5806\u9876\u7684\u5143\u7d20\u5148.\n\nfor ( i = 2 * summit_pos; i &lt;= tail_pos; i *= 2 )\n\n{\n\nif ( inc )  \/\/ \u8c03\u6574\u5c0f\u9876\u5806\n\n{\n\nif ( i &lt; tail_pos &amp;&amp; heap[i]._solved_count > heap[i+1]._solved_count )\n\ni++;\n\nif ( ! (heap[0]._solved_count > heap[i]._solved_count) )\n\nbreak;\n\n}\n\nelse  \/\/ \u8c03\u6574\u5927\u9876\u5806\n\n{\n\nif ( i &lt; tail_pos &amp;&amp; heap[i]._solved_count < heap[i+1]._solved_count )\n\ni++;\n\nif ( ! (heap[0]._solved_count < heap[i]._solved_count) )\n\nbreak;\n\n}\n\nheap[summit_pos] = heap[i];\n\nsummit_pos = i;\n\n}\n\nheap[summit_pos] = heap[0];\n\n}\n\n\n\n\/** \u8c03\u6574\u5806.\u4ece\u4e0b\u5f80\u4e0a\u8c03\u6574.\n\n* @param heap \u5806\u7684\u9996\u5730\u5740.\u7528\u987a\u5e8f\u8868\u5b58\u653e\u5806.\u4f46\u4e0d\u7528\u4e0b\u6807\u4e3a0\u7684\u5143\u7d20.\u8fd9\u4e2a\u5143\u7d20\u53ef\u7528\u6765\u4f5c\u4e34\u65f6\u5b58\u50a8.\n\n* @param tail_pos \u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u4f4d\u7f6e.tail_pos &gt; 0\n\n* @param inc \u662f\u5426\u5efa\u5c0f\u9876\u5806.\u5982\u679cfalse\u5219\u5927\u9876\u5806.\n\n*\/\n\nvoid adjust_heap_bottom2top(heap_elem_t heap[], int tail_pos, bool inc)\n\n{\n\nint i;\n\nheap[0] = heap[tail_pos];\n\nfor ( i = tail_pos; i &gt; 1; i \/= 2 )\n\n{\n\nint parent_pos = i \/ 2;\n\nif ( inc )  \/\/ \u8c03\u6574\u5c0f\u9876\u5806\n\n{\n\nif ( heap[parent_pos]._solved_count > heap[0]._solved_count )\n\n{\n\nheap[i] = heap[parent_pos];\n\n}\n\nelse\n\n{\n\nbreak;\n\n}\n\n}\n\nelse  \/\/ \u8c03\u6574\u5927\u9876\u5806\n\n{\n\nif ( heap[parent_pos]._solved_count < heap[0]._solved_count )\n\n{\n\nheap[i] = heap[parent_pos];\n\n}\n\nelse\n\n{\n\nbreak;\n\n}\n\n}\n\n}\n\n\n\nheap[i] = heap[0];\n\n}\n\n5 \u7a0b\u5e8f\u6ce8\u91ca\u6e05\u5355\uff08\u91cd\u8981\u8fc7\u7a0b\u7684\u8bf4\u660e\uff09;\n\n\/\/ poor_guy.cpp : Defines the entry point for the console application.\n\/\/\n\n#include &lt;algorithm&gt;\n#include &lt;string&gt;\n#include &lt;vector&gt;\n#include &lt;string.h&gt;\n#include &lt;stdio.h&gt;\n\nusing namespace std;\n\ntemplate&lt;typename T&gt; class my_vector\n{\npublic:\nmy_vector(T* addr)\n{\nm_ary = addr;\nm_ava_idx = 0;\n}\n~my_vector()\n{\n\/\/  delete []m_ary;\n}\n\nT&amp; operator[](int index)\n{\nreturn m_ary[index];\n}\n\nvoid push_back(const T&amp; v)\n{\nm_ary[m_ava_idx++] = v;\n}\n\nvoid resize(int size)\n{\nm_ava_idx = size;\n}\n\nvoid shrink(int dec)\n{\nm_ava_idx -= dec;\n}\n\nint size()\n{\nreturn m_ava_idx;\n}\nprivate:\nT*   m_ary;\nint  m_ava_idx;\n};\n\n\/\/ \u5806\u7684\u7ed3\u70b9\u5b9a\u4e49\nint g_name_pool_index = 0;\nchar g_name_pool[100001][11];\n\nstruct heap_elem_t\n{\n\/\/ string _name;\nint _name_index;\nint _solved_count;\n};\n\nheap_elem_t g_heap_elems0[50002];\nheap_elem_t g_heap_elems1[50002];\n\nstruct heap_elem_less_comparator\n{\nbool operator()(const heap_elem_t&amp; left,  const heap_elem_t&amp; right)\n{\nreturn left._solved_count &lt; right._solved_count;\n}\n};\n\nstruct heap_elem_larger_comparator\n{\nbool operator()(const heap_elem_t&amp; left,  const heap_elem_t&amp; right)\n{\nreturn left._solved_count &gt; right._solved_count;\n}\n};\n\nheap_elem_less_comparator less_comp;\nheap_elem_larger_comparator larger_comp;\n\n\/************************************************************************\/\n\/* inc \u4e3a\u771f\u65f6\u8c03\u6574\u4e3a\u5c0f\u9876\u5806\uff0c\u4e3afalse\u65f6\u8c03\u6574\u4e3a\u5927\u9876\u5806\u3002                      *\/\n\/************************************************************************\/\ninline void adjust_heap_up(heap_elem_t heap[], int tail_pos, bool inc)\n{\nif ( inc )\n{\npush_heap(heap+1, heap+tail_pos+1, larger_comp);\n}\nelse\n{\npush_heap(heap+1, heap+tail_pos+1, less_comp);\n}\n}\n\ninline void popup_the_top(heap_elem_t heap[], int tail_pos, bool inc)\n{\nif ( inc )\n{\npop_heap(heap+1, heap+tail_pos+1, larger_comp);\n}\nelse\n{\npop_heap(heap+1, heap+tail_pos+1, less_comp);\n}\n}\n\nint main(int argc, char* argv[])\n{\nconst int BUFF_LEN = 64;\nchar buff[BUFF_LEN];\nint case_count;  \/\/ \u8bb0\u6709\u591a\u5c11\u4e2acase;\nint contestant_count;\nmy_vector&lt;heap_elem_t&gt; littletop_heap(g_heap_elems0);\nmy_vector&lt;heap_elem_t&gt; bigtop_heap(g_heap_elems1);\nheap_elem_t contestant;\nstring name;\n\/\/ vector&lt;string&gt; output_vec;\n\nscanf(&quot;%d&quot;, &amp;case_count);\nfor ( int i = 0; i &lt; case_count; i++ )\n{\nlittletop_heap.resize(1);  \/\/ \u4e3a\u4e86\u65b9\u4fbf\u8ba1\u7b97.\u4e0b\u68070\u7684\u4f4d\u7f6e\u4e0d\u5b58\u5806\u7684\u5143\u7d20.\nbigtop_heap.resize(1);\ng_name_pool_index = 0;\ncontestant_count = 0;\n\nwhile(true)\n{\nscanf(&quot;%s&quot;, buff);\n\nint little_heap_count = littletop_heap.size() - 1;\nint big_heap_count = bigtop_heap.size() - 1;\n\nif ( buff[0] == &#39;Q&#39; )  \/\/ \u67e5\u8be2. Querry\n{\nif ( little_heap_count == big_heap_count || 0 == contestant_count )\n{\nprintf(&quot;No one!\\n&quot;);\n\/\/output_vec.push_back(&quot;No one!\\n&quot;);\n}\nelse\n{\nprintf(&quot;%s\\n&quot;, g_name_pool[littletop_heap[1]._name_index]);\n\/\/output_vec.push_back(g_name_pool[littletop_heap[1]._name_index]);\n\/\/output_vec.push_back(&quot;\\n&quot;);\n}\n}\nelse if ( buff[0] == &#39;E&#39; )  \/\/ \u7ed3\u675f.\n{\nif ( little_heap_count == big_heap_count || 0 == contestant_count )\n{\nprintf(&quot;Happy BG meeting!!\\n&quot;);\n\/\/output_vec.push_back(&quot;Happy BG meeting!!\\n&quot;);\n}\nelse\n{\nprintf(&quot;%s%s&quot;,g_name_pool[littletop_heap[1]._name_index], &quot; is so poor.\\n&quot;);\n\/\/output_vec.push_back(g_name_pool[littletop_heap[1]._name_index]);\n\/\/output_vec.push_back(&quot; is so poor.\\n&quot;);\n}\n\nbreak;\n}\nelse if( buff[0] == &#39;A&#39; )\/\/ \u52a0\u5165\u53c2\u8d5b\u8005\u6570\u636e.\n{\ncontestant_count ++;\n\nscanf(&quot;%s&quot;, g_name_pool[g_name_pool_index]);\ncontestant._name_index = g_name_pool_index;\ng_name_pool_index++;\nscanf(&quot;%d&quot;, &amp;contestant._solved_count);\n\nif ( 1 == contestant_count )  \/\/ \u7b2c\u4e00\u4e2a\u53c2\u8d5b\u8005\u6570\u636e.\n{\nlittletop_heap.push_back(contestant);\n}\nelse if ( little_heap_count == big_heap_count )  \/\/ \u4e24\u4e2a\u5806\u7684\u5143\u7d20\u76f8\u7b49.\n{\n\/\/ \u65b0\u5143\u7d20\u5927\u4e8e\u5927\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\uff0c\u6240\u4ee5\u63d2\u5165\u5c0f\u9876\u5806.\nif ( contestant._solved_count &gt;= bigtop_heap[1]._solved_count )\n{\nlittletop_heap.push_back(contestant);\nadjust_heap_up(&amp;littletop_heap[0], littletop_heap.size()-1, true);\n}\nelse\n{\nheap_elem_t top = bigtop_heap[1];\npopup_the_top(&amp;bigtop_heap[0], bigtop_heap.size()-1, false);\nbigtop_heap.shrink(1);\n\nbigtop_heap.push_back(contestant);\nadjust_heap_up(&amp;bigtop_heap[0], bigtop_heap.size()-1, false);\n\nlittletop_heap.push_back(top);\nadjust_heap_up(&amp;littletop_heap[0], littletop_heap.size()-1, true);\n}\n}\nelse  \/\/ \u4e0d\u7b49.\u53ea\u53ef\u80fd\u662f\u5c0f\u9876\u5806\u6bd4\u5927\u9876\u5806\u591a1.\n{\nif ( contestant._solved_count &gt; littletop_heap[1]._solved_count )\n{\nlittletop_heap.push_back(contestant);\nadjust_heap_up(&amp;littletop_heap[0], littletop_heap.size()-1, true);\n\nheap_elem_t top = littletop_heap[1];\npopup_the_top(&amp;littletop_heap[0], littletop_heap.size()-1, true);\nlittletop_heap.shrink(1);\n\nbigtop_heap.push_back(top);\nadjust_heap_up(&amp;bigtop_heap[0], bigtop_heap.size()-1, false);\n}\nelse\n{\nbigtop_heap.push_back(contestant);\nadjust_heap_up(&amp;bigtop_heap[0], bigtop_heap.size()-1, false);\n}\n}\n}\n}\n\nif ( i + 1 &lt; case_count )\n{\nprintf(&quot;\\n&quot;);\n\/\/output_vec.push_back(&quot;\\n&quot;);\n}\n}\n\n\/\/for ( int i = 0; i &lt; output_vec.size(); i++ )\n\/\/{\n\/\/ cout &lt;&lt; output_vec[i];\n\/\/}\n\nreturn 0;\n}\n<\/pre>\n<p>&nbsp;<\/p>\n<\/p><\/div>\n<div>&nbsp;<\/div>\n<div>\/\/\/\/\/\/\/\/ \u4e0a\u9762\u7684\u4ee3\u7801\u5728\u4e2d\u5c71\u5927\u5b66ACM\u7f51\u7ad9 www.soj.me \u4e0a\u901a\u8fc7.\u76ee\u524d\u7684\u6210\u7ee9\u662f\u7b2c14\u540d.<\/div>\n<div>&nbsp;<\/div>\n<div>Rank &nbsp;14 &nbsp; &nbsp;2011-12-07 10:00:19 &nbsp; &nbsp;0.18 sec &nbsp; &nbsp;2160 KB &nbsp; &nbsp;6971 Bytes &nbsp; &nbsp; C++ &nbsp; zausiu<\/div>\n<div>&nbsp;<\/div>\n<div>\u6ce8\u610f\u4e0a\u9762\u7684\u4ee3\u7801\u7edd\u4e0d\u80fd\u7528C++\u7684\u6807\u51c6IO cin cout \u505a\u8f93\u5165\u8f93\u51fa.\u5982\u679c\u7528C++\u7684IO\u6d41\u4f1a\u9020\u6210\u8d85\u65f6\u3002\u6211\u4e3a\u4e86\u8c03\u8fd9\u4e2a\u8d85\u65f6\u95ee\u9898\u8c03\u4e86\u6574\u6574\u4e00\u5929\uff01\u6b7b\u6d3b\u60f3\u4e0d\u5230\u662f\u56e0\u4e3aC++ IO\u7684\u95ee\u9898.\u7ae5\u978b\uff0c\u4e00\u5b9a\u8981\u7528 scanf \u548c printf \u554a\u3002\u9762\u5bf9\u5341\u4e07\u7ea7\u7684IO\uff0c\u5c24\u5176\u662f\u5728\u505aACM\u9898\uff0ccin cout \u662f\u9b54\u9b3c\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>\u539f\u56e0\u662f\uff1a<\/div>\n<div>&nbsp;<\/div>\n<div>More should be noted about I\/O operations in C++. Due to their complex underlying implementation &nbsp;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.<\/div>\n<div>&nbsp;<\/div>\n<div>6 \u6d4b\u8bd5\u6570\u636e;<\/div>\n<div>&nbsp;<\/div>\n<div>\u7528\u4e00\u4e2a\u7b80\u5355\u7684BASH\u811a\u672c\u6765\u521b\u5efa\u6d4b\u8bd5\u7528\u4f8b\u3002<\/div>\n<div>&nbsp;<\/div>\n<div>\n<pre class=\"brush:other\">#! \/bin\/bash\n\nINDEX=1\n\nSHRESHOLD=100000   \/\/ \u5efa\u5341\u4e07\u6761\u6570\u636e.\n\n\n\nwhile [ <span class=\"katex math inline\">INDEX -lt<\/span>SHRESHOLD ]\n\ndo\n\necho &quot;ADD name<span class=\"katex math inline\">INDEX<\/span>RANDOM&quot;\n\nlet &quot;INDEX=$INDEX+1&quot;\n\ndone<\/pre>\n<p>&nbsp;<\/p>\n<\/p><\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>7 \u5bf9\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u65b9\u9762\u7684\u5206\u6790.<\/div>\n<div>&nbsp;<\/div>\n<div>\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(log n), \u7a7a\u95f4\u590d\u6742\u5ea6\u662f O(n).<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>\u9644\u539f\u9898\uff1a<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>1022. Poor contestant Prob<\/div>\n<div>&nbsp;<\/div>\n<div>Description<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>As everybody known, &ldquo;BG meeting&rdquo; is very very popular in the ACM training team of ZSU.<\/div>\n<div>After each online contest, they will go out for &ldquo;smoking&rdquo;. Who will be the poor ones that have to BG the others? Of course, the half who solve less problems.<\/div>\n<div>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.<\/div>\n<div>Strange rule, isn`t it?<\/div>\n<div>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.<\/div>\n<div>Note that: Every contestant solves different number of problems. The total number of the contestants will not exceed 10^5.<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>Input<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>There are several cases in the input. The first line of the input will be an integer M, the number of the cases.<\/div>\n<div>Each case is consisted of a list of commands. There are 3 types of commands.<\/div>\n<div>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).<\/div>\n<div>2.Query :<\/div>\n<div>3.End :End of the case.<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>Output<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>1.For the Query command: If the current number of contestants is odd, the program should output the poor contestant&rsquo;s name currently even if there is only one contestants, otherwise, just out put &ldquo;No one!&rdquo; (without quotes).<\/div>\n<div>2.For the End command:<\/div>\n<div>If the total number of contestants in the data base is even, you should out put &ldquo;Happy BG meeting!!&rdquo;(without quotes),otherwise, you should out put the &ldquo;xxx is so poor. &rdquo;(without quotes) where xxx is the name of the poor one.<\/div>\n<div>3.Each case should be separated by a blank line.<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>&nbsp;<\/div>\n<div>Sample Input<\/div>\n<div>&nbsp;<\/div>\n<div>2<\/div>\n<div>Add Magicpig 100<\/div>\n<div>Add Radium 600<\/div>\n<div>Add Kingfkong 300<\/div>\n<div>Add Dynamic 700<\/div>\n<div>Query<\/div>\n<div>Add Axing 400<\/div>\n<div>Query<\/div>\n<div>Add Inkfish 1000<\/div>\n<div>Add Carp 800<\/div>\n<div>End<\/div>\n<div>&nbsp;<\/div>\n<div>Add Radium 100<\/div>\n<div>Add Magicpig 200<\/div>\n<div>End<\/div>\n<div>Sample Output<\/div>\n<div>&nbsp;<\/div>\n<div>No one!<\/div>\n<div>Axing<\/div>\n<div>Radium is so poor.<\/div>\n<div>&nbsp;<\/div>\n<div>Happy BG meeting!!<\/div>\n<div>Problem Source<\/div>\n<div>&nbsp;<\/div>\n<div>ZSUACM Team Member<\/div>\n<div>&nbsp;<\/div>\n<\/div>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;\u89e3 &nbsp;\u9898 &nbsp;\u62a5 &nbsp;\u544a &nbsp; 1 1022 Poor contestant Prob\u539f\u9898\u4e2d\u6587\u5927\u610f; &nbsp; \u5bf9\u4e8e\u5927\u7ea6\u5341\u4e07\u6761\u6570\u636e\uff1a\u5982\u679c\u5171\u5947\u6570\u6761\u6570\u636e\u5219\u627e\u5230\u6700\u4e2d\u95f4\u90a3\u6761\u8bb0\u5f55\u3002\u5982\u679c\u6709\u5076\u6570\u6761\u8bb0\u5f55\u5219\u5ffd\u7565\u3002 &nbsp; 2 \u7b97\u6cd5\u601d\u60f3\u53ca\u89e3\u9898\u7528\u5230\u7684\u4e3b\u8981\u6570\u636e\u7ed3\u6784; &nbsp; \u56e0\u4e3a\u6570\u636e\u7684\u89c4\u6a21\u6bd4\u8f83\u5927\u3002\u5982\u679c\u7ed9\u5341\u4e07\u6761\u8bb0\u5f55\u6392\u5e8f\u7684\u8bdd\u663e\u7136\u4f1a\u8d85\u65f6\u3002\u8003\u8651\u5230\u9898\u76ee\u53ea\u9700\u8981\u627e\u5230\u6700\u4e2d\u95f4\u90a3\u6761\u3002\u6613\u60f3\u5230\u628a\u6570\u636e\u5e73\u5206\u6210\u4e24\u90e8\u5206\uff0c\u7b2c\u4e00\u90e8\u5206\u7684\u6570\u636e\u5168\u90e8\u5927\u4e8e\u7b2c\u4e8c\u90e8\u5206\u7684\u6570\u636e\u3002\u521b\u5efa\u4e24\u4e2a\u5806\u7ed3\u6784\u3002\u7b2c\u4e00\u90e8\u5206\u7684\u8f83\u5927\u6570\u636e\u5efa\u5927\u5c0f\u9876\u5806\uff0c\u7b2c\u4e8c\u90e8\u5206\u7684\u8f83\u5c0f\u6570\u636e\u5efa\u6210\u5927\u9876\u5806\u3002\u5728\u63d2\u5165\u6570\u636e\u7684\u8fc7\u7a0b\u4e2d\uff0c\u52a8\u6001\u7ef4\u62a4\u8fd9\u4e24\u4e2a\u5806\uff0c\u4f7f\u5c0f\u9876\u5806\u7684\u5143\u7d20\u6570\u7b49\u4e8e\u5927\u9876\u5806\u7684\u5143\u7d20\u6570\u6216\u8005\u5c0f\u9876\u5806\u7684\u5143\u7d20\u6bd4\u5927\u9876\u5806\u7684\u5143\u7d20\u591a\u4e00\u3002\u672c\u9898\u7528\u6027\u7ebf\u8868\u6765\u5b58\u50a8\u5806\u3002 &nbsp; 3 \u8be6\u7ec6\u89e3\u9898\u601d\u8def; &nbsp; \u56e0\u4e3a\u6700\u7ec8\u9700\u8981\u8f93\u51fa\u4e00\u4e2a\u5b57\u7b26\u4e32\u3002\u4e3a\u4e86\u8282\u7701\u62f7\u8d1d\u5b57\u7b26\u4e32\u7684\u5f00\u9500\uff0c\u628a\u5b57\u7b26\u4e32\u5b58\u5230\u4e00\u4e2a\u5b57\u7b26\u4e32\u6c60\u4e2d\uff0c\u800c\u6bcf\u4e2a\u5806\u4e2d\u7684\u5143\u7d20\u53ea\u7ef4\u62a4\u8fd9\u4e2a\u5b57\u7b26\u4e32\u6c60\u7684\u7d22\u5f15\u53f7\u3002 &nbsp; \u521d\u59cb\u65f6\uff0c\u5c0f\u9876\u5806\u548c\u5927\u9876\u5806\u7684\u5927\u5c0f\u90fd\u662f0\u3002 &nbsp; 1. \u5f53\u8f93\u5165\u7b2c\u4e00\u6761\u6570\u636e\u65f6\uff0c\u628a\u8fd9\u6761\u6570\u636e\u653e\u5165\u5c0f\u9876\u5806\u4e2d\u3002 &nbsp; 2. \u5f53\u8f93\u5165\u66f4\u591a\u6570\u636e\u65f6\uff1a &nbsp; 2.1 \u5982\u679c\u5c0f\u9876\u5806\u548c\u5927\u9876\u5806\u7684\u5143\u7d20\u4e2a\u6570\u4e00\u6837\u591a\u3002\u4e3a\u4fdd\u8bc1\u6dfb\u52a0\u65b0\u6570\u636e\u540e\uff0c\u6211\u4eec\u9700\u8981\u7684\u6700\u4e2d\u95f4\u7684\u6570\u636e\u5728\u5c0f\u9876\u5806\u7684\u4e0a\u90e8\u3002\u53c8\u5206\u4e24\u79cd\u60c5\u51b5\u5904\u7406\uff1a &nbsp; 2.1.1 \u5982\u679c\u5f85\u52a0\u5165\u6570\u636e\u5927\u4e8e\u6216\u7b49\u4e8e\u5927\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u3002\u5219\u628a\u8fd9\u4e2a\u5f85\u52a0\u5165\u6570\u636e\u52a0\u5165\u5c0f\u9876\u5806\u3002\u8c03\u6574\u5c0f\u9876\u5806. &nbsp; 2.1.2 \u5982\u679c\u5f85\u52a0\u5165\u6570\u636e\u5c0f\u4e8e\u5927\u9876\u5806\u7684\u5806\u9876\u5143\u7d20.\u5219\u628a\u5927\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u5f39\u51fa\u6dfb\u52a0\u5230\u5c0f\u9876\u5806\uff0c\u8c03\u6574\u8fd9\u4e24\u4e2a\u5806\u3002\u4e4b\u540e\uff0c\u628a\u5f85\u52a0\u5165\u6570\u636e\u52a0\u5165\u5927\u9876\u5806\u3002 &nbsp; 2.2 \u5982\u679c\u5c0f\u9876\u5806\u548c\u5927\u9876\u5806\u7684\u5143\u7d20\u4e2a\u6570\u4e0d\u4e00\u6837\u591a\u3002\u56e0\u4e3a\u524d\u9762\u7684\u7ea6\u5b9a\uff0c\u90a3\u4e48\u5fc5\u5b9a\u662f\u5c0f\u9876\u5806\u7684\u5143\u7d20\u4e2a\u6570\u6bd4\u5927\u9876\u5806\u7684\u5143\u7d20\u4e2a\u6570\u591a\u4e00\u4e2a\u3002\u4ecd\u7136\u5206\u4e24\u79cd\u60c5\u51b5\uff1a &nbsp; 2.2.1 \u5982\u679c\u5f85\u52a0\u5165\u6570\u636e\u5927\u4e8e\u5c0f\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u3002\u5219\u628a\u5f85\u52a0\u5165\u6570\u636e\u52a0\u5165\u5c0f\u9876\u5806\u5e76\u8c03\u6574\uff0c\u8c03\u6574\u540e\u628a\u5c0f\u9876\u5806\u7684\u5806\u9876\u5f39\u51fa\u52a0\u5165\u5927\u9876\u5806\u5e76\u8c03\u6574\u3002\u5c0f\u9876\u5806\u5728\u5f39\u51fa\u5806\u9876\u5143\u7d20\u540e\u518d\u8c03\u6574\u4e00\u6b21\u3002 &nbsp; 2.2.1 \u5982\u679c\u5f85\u52a0\u5165\u6570\u636e\u4e0d\u5927\u4e8e\u5c0f\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u3002\u5219\u628a\u8be5\u6570\u636e\u52a0\u5165\u5927\u9876\u5806\uff0c\u8c03\u6574\u5927\u9876\u5806\u3002 &nbsp; \u8f93\u5165\u7ed3\u675f\u65f6\u76f4\u63a5\u53d6\u5c0f\u9876\u5806\u7684\u5806\u9876\u5143\u7d20\u5373\u8981\u6c42\u7684\u89e3\u3002\u6839\u636e\u5143\u7d20\u4e2d\u7684\u5b57\u7b26\u4e32\u7d22\u5f15\u53ef\u4ee5\u62ff\u5230\u9700\u8981\u6253\u5370\u7684\u5b57\u7b26\u4e32\uff0c\u672c\u9898\u4e2d\u5373\u90a3\u4f4dpoor &hellip; <a href=\"https:\/\/ykyi.net\/?p=256\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;sicily 1022 Poor contestant Prob \u89e3\u9898\u62a5\u544a\u3002&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[108],"class_list":["post-256","post","type-post","status-publish","format-standard","hentry","category-tech_articles","tag-108"],"_links":{"self":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/posts\/256","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=256"}],"version-history":[{"count":0,"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/posts\/256\/revisions"}],"wp:attachment":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}