<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="Description">
蕊蕊有n部喜欢的番剧，每部番剧里面有m个妹子，每个妹子都有一个颜值。现在蕊蕊想从每部番剧里挑出一个妹子，总共挑出n个妹子，组成后宫团，后宫团的颜值是里面n个妹子的颜值和。显然，蕊蕊一共可以组成m^n个后宫团，现在她想知道这m^n个后宫团中，颜值和第K大的总颜值是多少。
若K>m^n，输出0
<p>蕊蕊一共可以组成3^2=9个后宫团，总颜值分别是：<br>
1+2=3,1+2=3,1+5=6<br>
4+2=6,4+2=6,4+5=9<br>
3+2=5,3+2=5,3+5=8<br>
其中第4大的是6</p>
</div><div class="part" title="Input">
第一行三个整数n,m,k(1&lt;=n&lt;=1000,1&lt;=m&lt;=500,1&lt;=k&lt;=1000)。
接下来n行，每一行表示一部番剧的信息。每行m个整数，表示该番剧里m个妹子的颜值a(1&lt;=a&lt;=100000)。
</div><div class="part" title="Output">
输出一个整数，表示颜值和第K大的后宫团总颜值。
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
2 3 4
1 4 3
2 2 5
</div><div class="output part" title="Sample Output">
6
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p>直接看的话很容易想到<strong>01背包第k大</strong><br>
但是显然时间复杂度会爆炸<br>
这里应该使用<strong>多路归并</strong></p>
<p>按照01背包的思路,我们可以一组一组来看<br>
给每一组从大到小排序<br>
然后将两组合并到一起<br>
这样,当将所有的都合并进来后,得到的数组就是前<code>k</code>大</p>
<p>问题转换为将 <code>a</code> <code>b</code> 两个数组按照<code>a+b</code>合并到一起<br>
如果枚举计算出所有的<code>a+b</code>显然时间复杂度太高<br>
而且当数组很大的时候,其实很多<code>a+b</code>的计算是完全没有意义的<br>
<div class='image'><a href='//static.oyohyee.com/post/aoj912.png' target='_blank' rel='noopener noreferrer'><img src="//static.oyohyee.com/post/aoj912.png" /></a></div><br>
如图,对于前5大,只有绿色部分是有用的</p>
<p>但是,对于前<code>k</code>大,我们计算两个数组前<code>√k</code>个的和显然又是不行的<br>
可以通过使用优先队列来满足我们的要求</p>
<p>我们以任意一列为基准,记录下用这一列的数分别加上另一列最大的数,插入到优先队列中<br>
这时优先队列里的最大值(队列最前的值)必然是所有结果中最大的那一个值<br>
将其插入到我们的结果数组中,然后从优先队列中删除它<br>
对于第二大的值,可能是<code>a[1]+b[0]</code>也有可能是<code>a[0]+b[1]</code><br>
因此我们还应该通过刚刚的<code>a[0]+b[0]</code>得到<code>a[0]+b[1]</code>插入到优先队列中<br>
……</p>
<p>以此类推,当最大值是<code>a[i]+b[j]</code>时,我们要将<code>a[i]+b[j+1]</code>插入到队列中<br>
(由于<code>a[i]+b[j]</code>是最大值,那么可以得知<code>a[m]+b[n] (m&lt;=i n&lt;=j)</code>已经从队列中删除,也即<code>a[m]+b[j]</code>已经插入到队列中)<br>
此时<strong>优先队列中的最大值必然是下一个最大值</strong></p>
<p>每次出队一个入队一个<br>
总共出队<code>k</code>次<br>
再加上优先队列本身的复杂度<code>O(log(n))</code><br>
总复杂度是 <code>O(klog(n))</code></p>
<p>整道题复杂度为<code>O(mklog(n))</code>  是一个可以接受的复杂度</p>
<h1 id="heading-2">代码</h1>
<p>{% fold 点击显/隐代码 %}```cpp 蕊蕊的后宫团 <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
#include <algorithm><br>
#include <cstdio><br>
#include <cstring><br>
#include <iostream><br>
#include <queue><br>
using namespace std;</p>
<p>const int maxn = 5005;<br>
const int maxm = 505;<br>
const int maxk = 2005;</p>
<p>int a[maxn][maxm];<br>
int n, m, k;<br>
int len;</p>
<p>bool compare(int a, int b) { return a &gt; b; }</p>
<p>struct node {<br>
int s, b;<br>
node(int _s, int _b) : s(_s), b(_b) {}<br>
bool operator&lt;(node a) const { return a.s &gt; s; }<br>
};</p>
<p>void merge(int *a, int *b, int *c) {<br>
priority_queue<node> Q;<br>
for (int i = 0; i &lt; len; i++)<br>
Q.push(node(a[i] + b[0], 0));</p>
<pre><code>len = 0;
for (int i = 0; i &lt; k &amp;&amp; !Q.empty(); i++) {
    ++len;
    node r = Q.top();
    Q.pop();
    c[i] = r.s;
    int t = r.b;
    if (t + 1 &lt; m)
        Q.push(node(r.s - b[t] + b[t + 1], t + 1));
}
</code></pre>
<p>}</p>
<p>int main() {<br>
while (~scanf(&quot;%d%d%d&quot;, &amp;n, &amp;m, &amp;k)) {<br>
for (int i = 0; i &lt; n; i++) {<br>
for (int j = 0; j &lt; m; j++)<br>
scanf(&quot;%d&quot;, &amp;a[i][j]);<br>
sort(a[i], a[i] + m, compare);<br>
}</p>
<pre><code>    len = m;
    for (int i = 1; i &lt; n; i++)
        merge(a[0], a[i], a[0]);

    // for(int i = 0;i &lt; max(m,k); i++)
    //     printf(&quot;%d &quot;,a[0][i]);
    // printf(&quot;\n&quot;);

    printf(&quot;%d\n&quot;, a[0][k - 1]);
}

return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">{% endfold %}</pre>

AOJ 912.蕊蕊的后宫团