Priority_Queue/1439.Find-the-Kth-Smallest-Sum-of-a-Matrix-With-Sorted-Rows/Readme.md
我们注意到，虽然array的组合有m^n个，但本题中的K不超过200.这说明我们是可以暴力找到第K小的sum！
我们设立一个presum数组，记录的是从第一行到第i-1行的前k小的权重和路径（每一行选一个数）。在处理第i行的时候，我们将presum里面的元素与第i行的元素两两组合相加，这样做多有200*40个新元素，我们排个序取前k个，这样就得到了更新后的presum数组。
逐行推进，处理完最后一行之后，presum就包含了前k个sum。
我们从小到大搜索sum。初始状态（即最小的sum）必然对应着每行取第一个元素。然后基于这个idx array，可以扩展出m个idx array，即将每行的指针移向该行的下一个，...将所有拓展出的array sum放在一个PQ里，弹出当前最小的array sum继续拓展... 可见，此题本质上是就N sorted list的归并排序。
注意的是，idx array可能会有重复，需要用一个集合来去重。比如[[1,2],[1,2]]，初始状态是{2, {0,0}}；第二轮会加入{3, {1,0}},{3, {0,1}}；在第三轮，第二轮的前者会导入{4, {1,1}}，后者也会导入{4,{1,1}}，这样就会将{1,1}这个组合重复计数两次。
我们设计函数checkOK来判断 if the number of arrays whose sum <= target is at least k. 如果返回true，则target可能是个解（因为或许有若干个array sum都是target），但可以尝试更小的。如果返回false，那么target肯定不是答案，我们需要将taget变大。
那么如何统计有多少个符合条件的array呢？如果是暴力搜索所有的可能再判断，那么会有n^m种组合。但本题的特点是每行都是递增的，我们可以设计算法只搜索sum<=target的从array，当count超过k的时候即可终止整个搜索，这样每次搜索只需要o(k)的时间复杂度。
具体的做法是，我们设置初始sum就是各行首元素的和，即默认array的组成是各行的首元素。我们逐行深度搜索。对于第i行，我们从首元素往后尝试每一列，如果算上mat[i][j]满足sum<=target，那么计数器就可以加一(此时的array意味着下面每一行都选择首元素)，然后以此sum为基准递归处理下一行（也是从mat[i+1][0]开始）。反之，如果第mat[i][j]的元素使得sum>target，那么就终止这个递归。
特别注意，因为初始sum对应了一个初始的array，计数器也要初始化为1. 以后只有在遇到j>0时才能更新计数器。
此题的一维版本是1918.Kth-Smallest-Subarray-Sum