P2085 最小函數(shù)值
題目?【多路歸并】
思路
多路合并的思想
每個函數(shù)為一路，每一路從1...開始單調(diào)遞增
維護指針數(shù)組
維護小根堆，每次取最小的元素，并修改指針
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10010;
struct F{
? ?int a,b,c;
? ?LL get(LL x) {
? ? ? ?return x*x*a+x*b+c;
? ?}
}f[N];
struct Node {
? ?LL v;
? ?int id;
? ?bool operator<(const Node& t) const {
? ? ? ?return v > t.v;
? ?}
};
int p[N];
priority_queue<Node> pq;
int main()
{
? ?int n,m;
? ?cin>>n>>m;
? ?for(int i=0; i<n; ++i) {
? ? ? ?int a,b,c;
? ? ? ?scanf("%d%d%d", &a, &b, &c);
? ? ? ?f[i] = {a,b,c};
? ?}
? ?vector<LL> res;
? ?for(int i=0; i<n; ++i) {
? ? ? ?pq.push({f[i].get(1), i});
? ? ? ?p[i] = 1;
? ?}
? ?
? ?while (res.size() < m) {
? ? ? ?auto t = pq.top();
? ? ? ?pq.pop();
? ? ? ?res.push_back(t.v);
? ? ? ?int& pp = p[t.id];
? ? ? ?pp++;
? ? ? ?pq.push({f[t.id].get(pp), t.id});
? ?}
? ?
? ?for(int i=0; i<m; ++i) {
? ? ? ?printf("%lld ", res[i]);
? ?}
? ?return 0;
}
?鏈接：https://www.dianjilingqu.com/478659.html
