UVA 11997 K个最小和

2023-10-30 12:12:04

UVA 11997

【题目描述】：给定k组数，每组k个数，从每组数中各取出一个数，然后把他们加和，在不的加和组合中，求其中的最小的k的数。K<=750

【算法分析】：K个最小和

【思路分析】：刚刚拿到这道题，感觉难以下手。所以先分析最朴素的算法。决策方案，k^k种，太大了。如果想先计算，再排序，空间上都不能存储。我们再分析题目条件，发现只要求出前K小的数。然后分析，我们现在手上有效的工具sort，如果对每一维排序，复杂度是5*10^7，说实话，我开始时觉得这个也很大了，但是如果不将所有的排序，假设有一维数据全是极小数，就悲剧了。现在我们得到的是k维全部从小到大排序的数字。因为只需要k个最小值，对于前两组，有用信息是两数加和的最小值，保留k个即可。经过k-1次求最小即可。精髓是优先队列实现，只要有k个当前最小出队就可以了。当a[i]+b[i]被选定为当前最小时，a[i]+b[i+1]可能试下一个最小数。

【完整代码】：

  1 //核心在于二路归并算法O（n）的复杂度，
  2 
  3 //而且只要求局部最优解，k个最小
  4 
  5 #include<iostream>
  6 
  7 #include<stdio.h>
  8 
  9 #include<string.h>
 10 
 11 #include<algorithm>
 12 
 13 #include<stdlib.h>
 14 
 15 #include<math.h>
 16 
 17 #include<queue>
 18 
 19 #include<vector>
 20 
 21 #include<map>
 22 
 23 #define MAXN 755+10
 24 
 25 #define MAXM 20000+5
 26 
 27 #define oo 9556531
 28 
 29 #define eps 0.000001
 30 
 31 #define PI acos(-1.0)//这个精确度高一些
 32 
 33 #define REP1(i,n) for(int i=0;i<(n);i++)
 34 
 35 #define REP2(i,n) for(int i=1;i<=(n);i++)
 36 
 37 using namespace std;
 38 
 39  
 40 
 41 int A[MAXN][MAXN];
 42 
 43 int n;
 44 
 45 struct Table
 46 
 47 {
 48 
 49     int x;
 50 
 51     int y;
 52 
 53     int cal;//表示A[i]+B[j]
 54 
 55     bool operator<(const Table& x) const{
 56 
 57         return cal>x.cal;
 58 
 59     }
 60 
 61 };
 62 
 63 void merge(int A[],int B[])//合并A，B，再存储到A中
 64 
 65 {
 66 
 67     priority_queue<Table> T;
 68 
 69     int C[MAXN];
 70 
 71 for(int i=0;i<n;i++)
 72 
 73 //构建A[0]+B[0],A[0]+B[1],......A[0]+B[n-1]
 74 
 75     {
 76 
 77         Table nt=(Table){0,i,A[0]+B[i]};
 78 
 79         T.push(nt);
 80 
 81     }
 82 
 83     int cnt=0;
 84 
 85     while (cnt<n)
 86 
 87     {
 88 
 89         Table nt=T.top();
 90 
 91         T.pop();
 92 
 93         C[cnt++]=nt.cal;
 94 
 95         if (nt.x+1>=n) continue;
 96 
 97         nt=(Table){nt.x+1,nt.y,A[nt.x+1]+B[nt.y]};
 98 
 99         T.push(nt);
100 
101     }
102 
103     for(int i=0;i<n;i++) A[i]=C[i];
104 
105 }
106 
107 int main()
108 
109 {
110 
111     while(cin>>n)
112 
113     {
114 
115         for(int i=0;i<n;i++)
116 
117         {
118 
119             for(int j=0;j<n;j++) cin>>A[i][j];
120 
121             sort(A[i],A[i]+n);//750*750*7,有超时危险
122 
123         }
124 
125         for(int i=1;i<n;i++)
126 
127         merge(A[0],A[i]);//将A[0]和A[i],存储在A[0]
128 
129         cout<<A[0][0];
130 
131         for(int i=1;i<n;i++) cout<<" "<<A[0][i];
132 
133         cout<<endl;
134 
135     }
136 
137     return 0;
138 
139 }

【关键词】：局部解，优先队列。

UVA 11997 K个最小和

码农公寓

相关文章