最小函數值洛谷2085 堆

2019-11-10 17:31:08

字體：大中小

來源：轉載

供稿：網友

題目描述

有n個函數，分別為F1,F2,…,Fn。定義Fi(x)=Ai*x^2+Bi*x+Ci (x∈N*)。給定這些Ai、Bi和Ci，請求出所有函數的所有函數值中最小的m個（如有重復的要輸出多個）。

輸入格式：

輸入數據：第一行輸入兩個正整數n和m。以下n行每行三個正整數，其中第i行的三個數分別位Ai、Bi和Ci。Ai<=10，Bi<=100，Ci<=10 000。

輸出格式：

輸出數據：輸出將這n個函數所有可以生成的函數值排序后的前m個元素。這m個數應該輸出到一行，用空格隔開。

說明

數據規模：n,m<=10000

Analysis

題意直接粗暴，不知道要怎么說了開一個優先隊列記錄函數類型、當前x的值一開始把所有函數的最小值壓進去，然后此時的堆頂一定是最小的那么我們把堆頂的x+1再壓回去，如此做m次

重裝系統之后什么都沒了，氣死

Code

#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <iostream>#include <algorithm>#include <string>#include <vector>#include <deque>#include <list>#include <set>#include <map>#include <stack>#include <queue>#include <numeric>#include <iomanip>#include <bitset>#include <sstream>#include <fstream>#define debug puts("-----")#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)#define fill(x, t) memset(x, t, sizeof(x))#define f(x, a, b, c) x * x * a + x * b + c#define pb push_back#define PI (acos(-1.0))#define EPS (1e-8)#define INF (1<<30)#define ll long long#define db double#define ld long double#define N 20001#define E N * 8 + 1#define MOD 100000007#define L 255using namespace std;vector<int> a, b, c;struct pos{ int x, type; bool Operator >(const pos &r) const{ pos l = *this; return f(l.x, a[l.type], b[l.type], c[l.type]) <= f(r.x, a[r.type], b[r.type], c[r.type]); } bool operator <(const pos &r) const{ pos l = *this; return f(l.x, a[l.type], b[l.type], c[l.type]) > f(r.x, a[r.type], b[r.type], c[r.type]); }};inline int read(){ int x = 0, v = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-'){ v = -1; } ch = getchar(); } while (ch <= '9' && ch >= '0'){ x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * v;}int main(void){ int n = read(), m = read(); rep(i, 1, n){ a.pb(read()); b.pb(read()); c.pb(read()); } PRiority_queue<pos> heap; rep(i, 0, a.size() - 1){ heap.push((pos){1, i}); } while (m --){ pos now = heap.top(); heap.pop(); printf("%d ", f(now.x, a[now.type], b[now.type], c[now.type])); heap.push((pos){now.x + 1, now.type}); } puts("/n"); return 0;}

上一篇：筆試面試中涉及位運算的題目總結（一）

下一篇：uvm_object的理解