最小函数值洛谷2085 堆

2019-11-10 16:49:41

字体：大中小

来源：转载

供稿：网友

题目描述

有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;}

上一篇：继承与派生（一）

下一篇：网络流Dinic