【UVA–11997 K Smallest Sums 】

·哦，这题要用优先队列？那大米饼就扔一个手写堆上去吧！

·英文题，述大意：

输入n个长度为n的序列(题中是k，2<=k<=750)。一种结果定义为：从每个序列中都要挑选一个数加起来。挑选的不同种结果含有的元素可以重复，现在你需要求出在所有的nⁿ个结果中，找到其中最小的n个结果，然后按照从小到大顺序输出这n个结果。

·分析：

我们可以从简单情况加以考虑以得到普遍结论。

当只有1个序列时，那么就直接排个序就可以了(虽然不在数据范围里)。

当只有两个序列，也就是挑选出两个数（来自不同序列）的和我们要的结果。首先，我们怎么取得最小的那个和？毫无疑问，就是这个序列两个的最小数的和。那么第二小的数怎么取得？嗯嗯，肯定是这样：

第二小数=Min(1序列最小数+2序列第二小数,1序列第二小数+2序列最小数)

这样一直思考下去，现在我们知道了第i小的结果，要的到第(i+1)小的结果，就有两种选择加以比较。为了便于我们找到单个序列中第i大，我们给所有序列从小到大排序。

排序后，我们可以知道一个这样的结论：假设现在选择的第p大的组合是a[i]+b[j](注意，排好序了的)，那么第p大肯定不会去考虑a[i]+b[j+1]，因为a[i]+b[j]<a[i]+b[j+1]。这句奇怪的话只是想说明一个问题，在a[i]+b[j]都还没有被选为答案时，a[k]+b[t](k>=i,t>=j,且等号不同时成立)肯定不用管（管的意思是拿去进行Min的比较）。

快速维护大小关系，我们可以使用优先队列，将各式各样的组合塞进去。但是我们把所有的压进去，时间耗费太多（n*n啊！）。所以，使用上文的结论，那么上文在CODE中的意义是，a[i]+b[j]在优先队列中时,a[k]+b[t]无需存在。当我们挑选第k大的结果时，就是队首元素啦。那么接下来怎么维护？我们是用有序表：（注意a,b还是排好序了的）

a₁+b₁<=a₁+b₂<=a₁+b₃……<=a₁+b_n

a₂+b₁<=a₂+b₂<=a₂+b₃……<=a₂+b_n

这样做的话，我们维护了a的有序，那么对于每个组合，当a[i]+b[j]出队被选为答案后，我们就立刻将a[i]+b[j+1](前提是j+1<=n)加入队列作为将来可能的答案。到此我们可以推而广之，有n个序列时，我们输入一个b就和合并一次，将最小的答案直接塞到a中，操作n-1次合并，就完事啦。

手写了一个小堆堆，但是这道题数据小，手写堆没发挥优势。

代码来了：

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define Exchange(a,b) a^=b^=a^=b
 4 #define go(i,a,b) for(int i=a;i<=b;i++)
 5 using namespace std;const int N=752;
 6 int n,a[N],b[N],val[N],I[N];
 7 struct Heap
 8 {    
 9     int sz,cur[N],fa,v;
10     inline void Up_Adjust(int u)
11     {
12         fa=u>>1;while(u!=1&&val[cur[fa]]>val[cur[u]])
13         Exchange(cur[fa],cur[u]),fa=(u=fa)>>1;
14     }
15     inline void Down_Adjust(int u)
16     {
17         v=u<<1;while(v<=sz){v+=val[cur[v]]>val[cur[v+1]]&&v<sz;
18         if(val[cur[v]]>=val[cur[u]])return;
19         Exchange(cur[u],cur[v]);v=(u=v)<<1;}
20     }
21     inline void Insert(int i){cur[++sz]=i,Up_Adjust(sz);}
22     inline void Delete(){Exchange(cur[1],cur[sz]);sz--;Down_Adjust(1);}
23 }q;
24 int main()
25 {
26     while(~scanf("%d",&n))
27     {
28         go(i,1,n)scanf("%d",&a[i]);sort(a+1,a+n+1);
29         go(k,2,n)
30         {
31             go(i,1,n)scanf("%d",&b[i]);sort(b+1,b+n+1);q.sz=0;
32             go(i,1,n)val[i]=a[i]+b[1],I[i]=1,q.Insert(i);
33             go(j,1,n){int i=q.cur[1];a[j]=val[i];q.Delete();
34             if(I[i]<n)val[i]+=-b[I[i]]+b[I[i]+1],I[i]++,q.Insert(i);}
35         }
36         printf("%d",a[1]);go(i,2,n)printf(" %d",a[i]);puts("");
37     }
38     return 0;
39 }//Paul_Guderian

这是一段很长很长的旅程，用尽所有的时光永无止境

我不停地奔跑呼喊和追寻，在我的路上寻找生命的意义。————汪峰《我的路》