序列合并

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Comparator;
import java.util.PriorityQueue;

class Node {
    public int n;        // 序列通项公式中的自变量
    public int idx;      // 序列编号
    public long val;     // 将自变量带入序列通项中算得的值
    public Node(int n, int idx, long val) {
        this.n = n;
        this.idx = idx;
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());
        int[][] coefficient = new int[k][8];
        for(int i = 0; i < k; i++){
            String[] params = br.readLine().trim().split(" ");
            for(int j = 0; j < 8; j++)
                coefficient[i][7 - j] = Integer.parseInt(params[j]);
        }
        int n = Integer.parseInt(br.readLine().trim());
        // 构建一个容量为k的堆
        PriorityQueue<Node> heap = new PriorityQueue<>(k, new Comparator<Node>(){
            @Override
            public int compare(Node n1, Node n2){
                // 因为compare返回int，而Node.val类型为long，所以要改写成如下的形式
                if(n1.val > n2.val)
                    return 1;
                else if(n1.val < n2.val)
                    return -1;
                else
                    return 0;
            }
        });
        int count = 0;
        long topN = 0;
        // 先令n=1，带入k个序列公式计算出k个数加入堆
        for(int i = 0; i < k; i++)
            heap.offer(new Node(1, i, sequence(coefficient[i], 1)));
        // 到了第n小的数字就退出循环，打印第n小的数字
        while(count < n){
            Node cur = heap.poll();
            topN = cur.val;
            // 由cur.idx可以知道是哪个序列的数字出队，接下来需要在这个序列中补数
            cur.n ++;             // 自变量自增
            cur.val = sequence(coefficient[cur.idx], cur.n);   // 计算新的值
            heap.offer(cur);      // 向堆中补数
            count ++;
        }
        System.out.println(topN);
    }

    // 计算系数为params的序列在自变量为n时的值
    private static long sequence(int[] params, int n) {
        long val = 0;
        for(int i = 0; i < params.length; i++)
            val += params[i] * Math.pow(n, i);
        return val;
    }
}

#include<bits/stdc++.h>
using namespace std;

const int N = 8;
struct Node{
    long value;
    int id;
};

struct cmp{
    bool operator()(const Node& a, const Node& b){
        return a.value > b.value;
    }
};

int compute(vector<int>& seq, int n){
    //f=((((((a7*n +a6)*n +a5)*n +a4)*n +a3)*n +a2)*n +a1)*n +a0
    long ret = seq[0];
    for(int i=1; i<N; ++i){
        ret = ret*n + seq[i];
    }
    return ret;
}

int main(){
    int k=0, n=0;
    scanf("%d", &k);
    vector<vector<int>> seq(k, vector<int>(N, 0));
    for(int i=0; i<k; ++i){
        for(int j=0; j<N; ++j){
            scanf("%d", &seq[i][j]);
        }
    }
    scanf("%d", &n);
    // k路归并
    priority_queue<Node, vector<Node>, cmp> q;
    vector<int> next(k, 1);
    long val = 0;
    for(int i=0; i<k; ++i){
        val = compute(seq[i], next[i]);
        q.push({val, i});
        ++next[i];
    }
    while(--n){
        Node cur = q.top(); q.pop();
        val = compute(seq[cur.id], next[cur.id]);
        q.push({val, cur.id});
        ++next[cur.id];
    }
    // 第n个值
    cout<< q.top().value << endl;
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
	static class Node{
		Node next=null;
		int val;
		public Node(int val) {
			this.val=val;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		int k =  scanner.nextInt();
		ArrayList<Integer> arr = new ArrayList<Integer>();
		for(int i=0;i<k;i++) {
			for(int j=0;j<8;j++) {
				arr.add(scanner.nextInt());
			}
		}
		int n= scanner.nextInt();
		scanner.close();
		Node head=null,curNode=null,preNode=null;
		int count=0;
		int[] curNums = new int[k];
		Go:
		for(int m=1;m<=n;m++) {
			Iterator<Integer> it = arr.iterator();
			for(int i=0;i<k;i++) {
				int cur=0;
				for(int j=0;j<8;j++) {
					cur+=(int)it.next()*Math.pow(m, 7-j);
				}
				curNode = new Node(cur);
				if(head ==null) {
					head=curNode;
					count++;
				}else {
					Node temp = head;
					if(cur>=head.val&&count<n) {
						head = new Node(cur);
						head.next=temp;
						count++;
					}else if(cur<head.val){
						while(temp.val>cur&&temp!=null) {
							preNode=temp;
							temp=temp.next;
						}
						curNode.next=temp;
						preNode.next=curNode;
						if(count>=n) {
							head=head.next;
							Arrays.sort(curNums);
							if(curNums[0]>=head.val) break Go;
						}
						count++;
					}   
				}
				if(count>=n-1) {
					curNums[i]=cur;
				}
			}
		}
		System.out.println(head.val);

	}

}