解题思路

这是一道关于多项式序列的题目。主要思路如下:

  1. 问题分析:

    • 给定 个7次多项式,每个多项式只有两个非零系数
    • 需要找到所有序列中第 小的数字
    • 每个序列是将 代入多项式得到的值
  2. 优化思路:

    • 使用优先队列维护 个序列的当前最小值
    • 每次取出最小值后,将同一序列的下一个值加入队列
    • 使用霍纳法则(Horner's method)优化多项式计算
  3. 关键点:

    • 使用小根堆维护当前最小值
    • 记录每个序列的下一个位置
    • 高效计算多项式值

代码

#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) {
    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));
    
    // 读入k个多项式的系数
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < N; j++) {
            scanf("%d", &seq[i][j]);
        }
    }
    scanf("%d", &n);
    
    // 初始化优先队列和每个序列的下一个位置
    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];
    }
    
    // 找第n小的数
    while(--n) {
        Node cur = q.top(); q.pop();
        val = compute(seq[cur.id], next[cur.id]);
        q.push({val, cur.id});
        ++next[cur.id];
    }
    
    cout << q.top().value << endl;
    return 0;
}
import java.util.*;

public class Main {
    static class Node {
        long value;
        int id;
        
        Node(long value, int id) {
            this.value = value;
            this.id = id;
        }
    }
    
    static long compute(int[] seq, int n) {
        long ret = seq[0];
        for(int i = 1; i < 8; i++) {
            ret = ret * n + seq[i];
        }
        return ret;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int[][] seq = new int[k][8];
        
        for(int i = 0; i < k; i++) {
            for(int j = 0; j < 8; j++) {
                seq[i][j] = sc.nextInt();
            }
        }
        int n = sc.nextInt();
        
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> 
            Long.compare(a.value, b.value));
        int[] next = new int[k];
        Arrays.fill(next, 1);
        
        for(int i = 0; i < k; i++) {
            long val = compute(seq[i], next[i]);
            pq.offer(new Node(val, i));
            next[i]++;
        }
        
        while(--n > 0) {
            Node cur = pq.poll();
            long val = compute(seq[cur.id], next[cur.id]);
            pq.offer(new Node(val, cur.id));
            next[cur.id]++;
        }
        
        System.out.println(pq.peek().value);
    }
}
from heapq import heappush, heappop

def compute(seq, n):
    ret = seq[0]
    for i in range(1, 8):
        ret = ret * n + seq[i]
    return ret

k = int(input())
seq = []
for _ in range(k):
    seq.append(list(map(int, input().split())))
n = int(input())

# 使用堆来维护最小值
heap = []
next_pos = [1] * k

# 初始化堆
for i in range(k):
    val = compute(seq[i], next_pos[i])
    heappush(heap, (val, i))
    next_pos[i] += 1

# 找第n小的数
for _ in range(n-1):
    val, idx = heappop(heap)
    new_val = compute(seq[idx], next_pos[idx])
    heappush(heap, (new_val, idx))
    next_pos[idx] += 1

print(heap[0][0])

算法分析

  • 时间复杂度:
    • 每次操作堆的时间为
    • 需要进行 次操作
  • 空间复杂度:
    • 优先队列存储 个元素
    • 存储 个序列的下一个位置