题目大意
给定n组数,每组数有若干个数组,在每一个数组中取一个数然后构成新的数组,求新数组里的值的总和最小的前m个
思路
先将第一组数存到一个数组中,然后将后面数组中的数加上第一组数的第一个后存入堆中(全部数组按升序排列)然后枚举两个数组中的值,和堆顶进行判断,如果小于堆顶就把堆顶替换掉,最后将堆里的值覆盖掉第一个数组,继续操作直至全部处理完,输出堆中的值
O(n*n*logn)
#include#include #include using namespace std; int arr1[1000000],arr2[1000000]; bool cam(int x,int y) { return x heap; int main() { int n,m,x; scanf("%d",&x); for (int o=1;o<=x;o++) { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d",&arr1[i]); sort(arr1+1,arr1+m+1,cam); for (int i=2;i<=n;i++) { for (int j=1;j<=m;j++) scanf("%d",&arr2[j]); sort(arr2+1,arr2+m+1,cam); for (int j=1;j<=m;j++) { int ll=arr1[1]+arr2[j]; heap.push(arr1[1]+arr2[j]); } for (int j=2;j<=m;j++) { for (int k=1;k<=m;k++) { int t=arr1[j]+arr2[k]; if (t
Comments NOTHING