POJ 2442 题目大意:
给出m个序列,每个序列有n个非负整数,每次从每一个序列中取出一个数(共m个数)求和(显然有 n^m 个和),求这些和数中前n个最小的数。
样例:(第一行是测试次数1,第二行是m和n,接下来是m个序列)
Sample Input
1
2 3
1 2 3
2 2 3
Sample Output
3 3 4
解题步骤:
1.将第一序列读入array1数组中,并按升序排序。
2.将第二序列数据读入array2数组中,并按升序排序。
将array2[0] + array1[i] ( 0<=i<=n-1)读入heap优先队列中建堆。
然后array2[1] + array1[i] (0<=i<=n-1),如果array2[1] + array1[i]比堆heap的顶点大,则退出,否则删除堆的顶点,插入array2[1] + array1[i]。然后是array2[2],...array2[n - 1]
3.将heap的数据拷贝到array1中,并对array1按升序排序
4.循环2,3步,直到所有数据读入完毕。
5.打印array1中的数据即为结果。
import java.util.Scanner;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Main{
private int[] array1;
private int[] array2;
PriorityQueue<Integer> heap;
public Main(){
}
private void go(){
Scanner in=new Scanner(System.in);
int t=in.nextInt();
while(t-->0){
int m=in.nextInt();
int n=in.nextInt();
array1=new int[n];
array2=new int[n];
//优先队列作堆使用,从大到小
heap=new PriorityQueue<Integer>(n,new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2) {
if(o1<o2)
return 1 ;
else if(o1>o2){
return -1;
}else{
return 0;
}
}
});
for(int i=0;i<n;i++)
array1[i]=in.nextInt(); //读入第一序列
Arrays.sort(array1); //排序,升序
for(int i=1;i<m;i++){ //处理第二到第m个序列
for(int j=0;j<n;j++){
array2[j]=in.nextInt(); //先读入第二序列,然后第三。。。
heap.offer(array1[0]+array2[j]);//建堆
}
Arrays.sort(array2); //升序排列
for(int k=1;k<n;k++)
for(int l=0;l<n;l++){
if(array1[k]+array2[l]>heap.peek()) //查看堆顶元素
break;
heap.poll(); //删除堆的顶点
heap.offer(array1[k]+array2[l]);
}
for(int k=n-1;k>=0;k--)
{
array1[k]=heap.poll(); //将heap的数据拷贝到array1中
}
}
System.out.printf("%d",array1[0]);
for(int i=1;i<n;i++)
System.out.printf(" %d",array1[i]);
System.out.println();
}
}
public static void main(String[] args){
Main ma=new Main();
ma.go();
}
}
分享到:
相关推荐
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
模拟题 要注意时间的处理 使用优先队列处理请求的事件 进行适当的运算符重载,可以简化代码
poj 2442 Sequence.md
NULL 博文链接:https://128kj.iteye.com/blog/1705139
用java的biginteger实现的poj1001,比较简单的方法
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
POJ 1328 java做!雷达问题!java版本!AC答案~
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
北大poj JAVA源码
poj 2785 4 Values whose Sum is 0 测试数据 解题报告: http://blog.csdn.net/qq7366020/article/details/8623208
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
poj 1654的代码,供大家参考,看有没有更好的方法
用Java代码实现POJ(PKU)上题2494!
pku acm 第3356题 AGTC Java代码,有详细的注释,动态规划
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj习题答案大家多多支持。
...