首页 > 代码库 > UVA.11997- K Smallest Sums, OJ4TH.368 - Magry's Sum I

UVA.11997- K Smallest Sums, OJ4TH.368 - Magry's Sum I

2024-08-16 09:54:29   219人阅读

感谢算法助教们给了这么一个好题...

题意：

给出n个数组，每个数组有n个元素，我们从每个数组中挑选一个元素，共计n个元素求和，得到共计 $ k^k $ 种sum，求sum中的最小n个值。

 

  1. 利用二分查找符合条件的最大sum值，dfs搜索判断二分条件。最坏时间复杂度 $O(n^{2}log(n*Max(a[i][j])) $
  2. 刘汝佳训练指南上给出了优先队列多路归并的思想。

思路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 }
View Code

 

思路2代码留坑

UVA.11997- K Smallest Sums, OJ4TH.368 - Magry's Sum I


联系
我们