首页 > 代码库 > UVA.11997- K Smallest Sums, OJ4TH.368 - Magry's Sum I
UVA.11997- K Smallest Sums, OJ4TH.368 - Magry's Sum I
感谢算法助教们给了这么一个好题...
题意：
给出n个数组，每个数组有n个元素，我们从每个数组中挑选一个元素，共计n个元素求和，得到共计 $ k^k $ 种sum，求sum中的最小n个值。
- 利用二分查找符合条件的最大sum值，dfs搜索判断二分条件。最坏时间复杂度 $O(n^{2}log(n*Max(a[i][j])) $
- 刘汝佳训练指南上给出了优先队列多路归并的思想。
思路1代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 7 int a[751][751]; 8 int pos[751]; 9 int n;10 int mid;11 int sum;12 int ans[1000];13 int cnt = 0;14 void dfs(int i)15 {16 if (sum > mid) return;17 ans[cnt ++] = sum;18 if (cnt > n) {19 return;20 }21 for (i; i < n && cnt < n; i ++)22 {23 if (pos[i] == n - 1) continue;24 25 ++pos[i];26 sum += a[i][ pos[i] ] - a[i][ pos[i] - 1 ];27 dfs(i);28 sum -= a[i][ pos[i] ] - a[i][ pos[i] - 1 ];29 --pos[i];30 }31 }32 33 int main()34 {35 while(~scanf("%d",&n))36 {37 for (int i = 0; i < n; i++)38 for (int j = 0; j < n; j++)39 scanf("%d",&a[i][j]);40 41 for (int i = 0; i < n; i++)42 sort(a[i],a[i] + n);43 44 memset(pos,0,sizeof pos);45 int l = -1, r = n*1000000;46 while(r-l > 1)47 {48 sum = 0;49 for (int i = 0; i < n; i++)50 sum += a[i][0];51 52 cnt = 0;53 mid = (l+r) / 2;54 dfs(0);55 if (cnt >= n) r = mid;56 else l = mid;57 }58 cnt = 0;59 sum = 0;60 for (int i = 0; i < n; i++)61 sum += a[i][0];62 63 mid = r - 1;64 dfs(0);65 sort(ans,ans+cnt);66 for (int i = 0; i < cnt; i++)67 printf("%d ",ans[i]);68 for (int i = cnt; i < n-1; i++)69 printf("%d ",r);70 printf("%d\n",r);71 }72 }
思路2代码留坑
UVA.11997- K Smallest Sums, OJ4TH.368 - Magry's Sum I
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。