首页 > 代码库 > poj2442（Sequence）
poj2442（Sequence）
题目地址：Sequence
题目大意;
给你m行，每行有n个数。 分别从每一行取一位数，然后加和。这样的数一定会构成m^n个。输出最小的n个即可。
解题思路：
思路： 因为，要每行都取一个，构成一个和sum。需要找出n个sum。 我们需要一行一行的找，不妨先设前两行的最小的n个sum是由第一行n个数和第二行的第一个数构成的。 存入c[]数组里，然后一次遍历第二行其他的数，看是否有小于c[]数组里最大的数，然后替换，这是前两行的最小的n个sum已经找到，存到了c[]数组， 然后找前三行，同样设让第三行的第一个数与数组c[]所有的数加和， 然后遍历第三行其他的数，看是否有小于c[]数组里最大的数。替换。以此类推。找到第m-1行 结束寻找，这时数组c[]里就是题目要求的数组。
实现：因为做的是堆和优先队列，所以优先想到用优先队列实现最大堆，这样Q.top（）始终存的是n个sum中最大的那个数，而且判断，替换后，优先队列自动从大到小排列。（ps：不知道不用优先队列，每次排序会不会超时。）注意：（剪枝时注意序列的排列，代码中有说明）。
代码1：正常做法 T：4000+
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector>10 #include <queue>11 #include <stack>12 #include <cmath>13 #include <list>14 #include <map>15 #include <set>16 using namespace std;17 /***************************************/18 #define ll long long19 #define int64 __int6420 /***************************************/21 const int INF = 0x7f7f7f7f;22 const double eps = 1e-8;23 const double PIE=acos(-1.0);24 const int d1x[]= {0,-1,0,1};25 const int d1y[]= {-1,0,1,0};26 const int d2x[]= {0,-1,0,1};27 const int d2y[]= {1,0,-1,0};28 const int fx[]= {-1,-1,-1,0,0,1,1,1};29 const int fy[]= {-1,0,1,-1,1,-1,0,1};30 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/31 /***************************************/32 void openfile()33 {34 freopen("data.in","rb",stdin);35 freopen("data.out","wb",stdout);36 }37 priority_queue<int> qi1;38 priority_queue<int, vector<int>, greater<int> >qi2;39 /**********************华丽丽的分割线,以上为模板部分*****************/40 const int M=2005;41 int s[M],sum[M];42 int main()43 {44 int cas;45 scanf("%d",&cas);46 priority_queue<int >Q;47 while(cas--)48 {49 int m,n;50 scanf("%d%d",&m,&n);51 int i,j,k;52 while(!Q.empty())53 Q.pop();54 for(i=0; i<n; i++)55 scanf("%d",&s[i]);56 for(i=1; i<m; i++)57 {58 for(j=0; j<n; j++)59 {60 scanf("%d",&sum[j]);61 }62 for(j=0; j<n; j++)63 Q.push(sum[0]+s[j]);64 int max;65 for(j=1; j<n; j++)66 for(k=0; k<n; k++)67 {68 max=sum[j]+s[k];69 if (max<Q.top())70 {71 Q.pop();72 Q.push(max);73 }74 }75 int d=0;76 while(!Q.empty())77 {78 s[d++]=Q.top();79 Q.pop();80 }81 }82 sort(s,s+n);83 printf("%d",s[0]);84 for(i=1; i<n; i++)85 printf(" %d",s[i]);86 printf("\n");87 }88 return 0;89 }
代码2：剪枝 T：800+（估计是数据的原因）
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector>10 #include <queue>11 #include <stack>12 #include <cmath>13 #include <list>14 #include <map>15 #include <set>16 using namespace std;17 /***************************************/18 #define ll long long19 #define int64 __int6420 /***************************************/21 const int INF = 0x7f7f7f7f;22 const double eps = 1e-8;23 const double PIE=acos(-1.0);24 const int d1x[]= {0,-1,0,1};25 const int d1y[]= {-1,0,1,0};26 const int d2x[]= {0,-1,0,1};27 const int d2y[]= {1,0,-1,0};28 const int fx[]= {-1,-1,-1,0,0,1,1,1};29 const int fy[]= {-1,0,1,-1,1,-1,0,1};30 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/31 /***************************************/32 void openfile()33 {34 freopen("data.in","rb",stdin);35 freopen("data.out","wb",stdout);36 }37 priority_queue<int> qi1;38 priority_queue<int, vector<int>, greater<int> >qi2;39 /**********************华丽丽的分割线,以上为模板部分*****************/40 const int M=2005;41 int s[M],sum[M];42 int main()43 {44 int cas;45 scanf("%d",&cas);46 priority_queue<int >Q;47 while(cas--)48 {49 int m,n;50 scanf("%d%d",&m,&n);51 int i,j,k;52 for(i=0; i<n; i++)53 scanf("%d",&s[i]);54 for(i=1; i<m; i++)55 {56 sort(s,s+n); //需要排序57 for(j=0; j<n; j++)58 {59 scanf("%d",&sum[j]);60 }61 for(j=0; j<n; j++)62 Q.push(sum[0]+s[j]);63 int max;64 for(j=1; j<n; j++)65 for(k=0; k<n; k++)66 {67 max=sum[j]+s[k];68 if (max>=Q.top()) //因为这个地方需要使后面的数都保证大于Q.POP(),所以需要对s数组排序。69 break;70 if (max<Q.top())71 {72 Q.pop();73 Q.push(max);74 }75 }76 int d=0;77 while(!Q.empty())78 {79 s[d++]=Q.top();80 Q.pop();81 }82 }83 sort(s,s+n);84 printf("%d",s[0]);85 for(i=1; i<n; i++)86 printf(" %d",s[i]);87 printf("\n");88 while(!Q.empty())89 Q.pop();90 }91 return 0;92 }
poj2442（Sequence）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。