Sequence(Poj2442)
Sequence(Poj2442)
题意:
有m个数列,每个数列n个值,每个序列中选取一个值可以组成n^m种不同的序列,求前n小的序列和。
Input
1
2 3
1 2 3
2 2 3
Output
3 3 4
分析:
用两个优先队列维护前n小和。首先将第一列n个数字放入从大到小的优先队列中,每次弹出一个最小值和下一行的每个元素相加,并放入另一个从小到大的优先队列中,当放满n个值时,每次求和结果先和队列中的top对比,若小于top则弹出并塞入这个和,否则舍弃这个较大和。这样维护的就是求和到第i行时的前n小序列和。当数列中n个元素都和下一列的元素求和完后,将这些前n小和又倒出来塞入从大到小的队列中,这样就和一开始对第一行的数列一样,每次选取一个最小值进行和后面的值求和,并将和塞入从小到大的优先队列中,这样反复倒腾最后加和到最后一行时仍然是所有数列求和的最小值,然后放入从大到小的数列中,依次弹出即是升序输出。
• 两组两组的看,首先要排序,然后从头开始找最小的N个和。
• 怎么找是个问题,对于第一组我们取i=1,第二组取j=1,然后a[1]+b[1]肯定是最小的,然后a[2]+b[1],a[1]+b[2]进入候选项,如果我们下一次选中了a[2]+b[1],那么我们又要将a[3]+b[1],a[2]+b[2]加入候选项。
• 但是我们要保证产生候选项不能重复,比如a[1]+b[2]和a[2]+b[1]都可以产生a[2]+b[2],所以我们要排除其中的一种,也就是说,我们要将候选项的下标计算变得有限制。
• 候选项的下标都是通过选中当前项的下标加一得到的,那么为了避免重复,我们要制定一种规则。假如规定为如果j+1,那么这个候选项被选中的时候i就不能更新。
- i=1,j=1
• 更新i=2,j=1, flag = true
• 更新i=1, j=2, flag = false
- 假如选中i=2,j=1,flag = true
• 由于是true,可以更新i=3,j=1,flag = true
• 更新i=2,j=2,flag = false
- 假如选中i=1,j=2,flag = false
• 由于false,不能更新i
• 更新i=1,j=3,flag = false
......
对于两个序列我们就可以a[0]+b[0],a[1]+b[0]一直到a[n-1]+b[0],然后是依次加a[1],这样我们就可以得到一个新的序列,如果只有两个序列,那我们的序列就是符合条件的,如果对于三个序列那就是两个序列组成的新序列看成新的a序列,第三个序列就是b序列,想一想,是不是?
这样依次迭代,到最后就是所求的m个序列组成的新序列,如果我们全部暴力存储,显然时间和空间开销都是非常大的,到最后跟直接m个序列暴力是没有区别的,达到n^m。 每次维护长为n的数组就可以啦
#include<stdio.h>///两个优先队列组合使用
#include<queue>
using namespace std;
int main()
{
int t,i,j,m,n,num;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
priority_queue<int ,vector<int>,less<int> >s;///一个优先级 从 小->大
priority_queue<int ,vector<int>,greater<int> >q;///一个优先级 从 大->小
for(i=1; i<=m; i++)///输入m列
{
if(i==1)///先将第一列作为基础塞入q队列中
{
for(j=0; j<n; j++)
{
scanf("%d",&num);
q.push(num);
}
}
else
{
int numd[n+10],sum;
for(j=0; j<n; j++)///几列,存入一个数组中
{
scanf("%d",&numd[j]);
}
while(q.size())///从q队列中,一个一个选出元素,分别与后面输入的数组中的每一个值相加
{
sum=q.top();///选出队首元素,记为sum
q.pop();///出列
for(j=0; j<n; j++)///和输入的数组中每个都加一遍
{
if(s.size()==n&&s.top()>sum+numd[j])///若超过或等于了n个元素,判断s队列中的队首(放入队列中的最大值)是否大于当前选出的数和数组中元素之和
{
s.pop();///若大于,弹出那个较大数,重新塞入求和而得的较小的数
s.push(sum+numd[j]);
}
else if(s.size()<n)///s队列中若没达到n个元素,加完就塞进去
{
s.push(sum+numd[j]);
}
}///这样一个循环下来,就将下一组数与当前q队列中的某一个元素相加完毕,并筛选出了前n个较小的求和数
}///while的下一轮将求和队列中的下一个数,并继续筛选求和数中的前n小值
while(s.size())///所有数筛选完毕此时在s队列中都是最小的前n个数
{
q.push(s.top());
s.pop();
}///每行完成更新后将求和结果统一塞回Q队列中准备下一行筛选求和
}
}
while(q.size())
{
printf("%d%c",q.top(),(q.size()-1==0)?'\n':' ');
q.pop();
}
}
return 0;
}
最新文章
- mysql进阶之存储过程
- MAC上向GitHub上上传自己的项目
- 防刷票机制研究和.NET HttpRequest Proxy
- 内存溢出VS内存泄漏
- SQL 关于apply的两种形式cross apply 和 outer apply(转)
- AD域修改组策略
- MySQL下全文索引
- 【CodeForces 621C】Wet Shark and Flowers
- ApplicationContext容器的设计原理
- php 修改上传文件大小
- Phpcms所有系统变量列表 Phpcms V9 文件目录结构
- 我对DFS的理解
- Python全栈开发记录_第五篇(装饰器)
- java创建对象 的初始化顺序
- 【leetcode】438. Find All Anagrams in a String
- Unable to cast object of type &#39;System.Int32&#39; to type &#39;System.Array&#39;.
- Redis随笔-rename效率问题
- Jmeter保存时,完美解决提示的“拒绝访问”
- 乘风破浪:LeetCode真题_030_Substring with Concatenation of All Words
- MySQL 分库备份