# 14252: 【原4252】函数值

### 题目描述

author: fur 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4252

# 函数值

## 样例输入1

2 9
1 0 0
1 2 0


## 样例输出1

-1 0 0 0 1 1 3 3 4


## 数据规模

$$0 < a_i$$

$$b_i \% (2 * a_i) = 0$$

$$b_i \% a_i = 0$$

$$n \leq 500$$
$$k \leq 500$$

$$n \leq 3000$$
$$k \leq 3000$$

$$n \leq 100000$$
$$k \leq 100000$$

## skyzh's solution

#include <stdio.h>
#include <iostream>
#include <cmath>
using namespace std;

template<typename T>
struct Heap {
T *data;
int cap, len;

Heap(int cap = 1024) : cap(cap + 1), len(0) {
data = new T[cap];
}

Heap(const Heap& that) : cap(that.cap), len(that.len) {
data = new T[cap];
memcpy(data, that.data, sizeof(T) * cap);
}

~Heap() { delete[] data; }

void push(const T &x) {
data[++len] = x;
swim(len);
}

T pop() {
swap(data[1], data[len--]);
sink(1);
return data[len + 1];
}

void top() {
return data[1];
}

bool less(int a, int b) {
if (a > len || b > len) return false;
return data[a] < data[b];
}

void swim(int idx) {
int _idx;
while (idx > 1 && less(idx, _idx = idx / 2)) {
swap(data[idx], data[_idx]);
idx = _idx;
}
}

void sink(int idx) {
int _idx;
while ((_idx = 2 * idx) <= len) {
if (_idx < len && less(_idx + 1, _idx)) _idx++;
if (less(idx, _idx)) break;
swap(data[idx], data[_idx]);
idx = _idx;
}
}

bool empty() {
return len == 0;
}
};

struct func_data {
int x, dx, y, id;
func_data(int x, int dx, int y, int id) : x(x), dx(dx), y(y), id(id) {}
func_data() {}
friend bool operator<(const func_data &a, const func_data &b) {
return a.y < b.y;
}
};

const int MAX_DATA = 100000;
int func[MAX_DATA][3] = { 0 };
Heap <func_data> heap(MAX_DATA * 3);
int n, k;

inline int evaluate(int x, int id) {
return func[id][0] * x * x + func[id][1] * x + func[id][2];
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
func[i][0] = a; func[i][1] = b; func[i][2] = c;
int mod = b % (2 * a);
double x = -b / (2.0 * a);
if (mod == 0) {
heap.push(func_data(x, 0, evaluate(x, i), i));
} else {
int x1 = floor(x);
int x2 = ceil(x);
heap.push(func_data(x1, -1, evaluate(x1, i), i));
heap.push(func_data(x2, 1, evaluate(x2, i), i));
}
}
func_data x;
for (int i = 0; i < k; i++) {
x = heap.pop();
printf("%d ", x.y);
if (x.dx == 0) {
heap.push(func_data(x.x - 1, -1, evaluate(x.x - 1, x.id), x.id));
heap.push(func_data(x.x + 1, 1, evaluate(x.x + 1, x.id), x.id));
} else {
heap.push(func_data(x.x + x.dx, x.dx, evaluate(x.x + x.dx, x.id), x.id));
}
}
return 0;
}


## zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, k, a[100005], b[100005], c[100005];
int ans[100005];
struct node{
int val, x, id;
node(){}
node(int v, int _x, int _id): val(v), x(_x), id(_id){}
bool operator <(const node& nd) const{
return val > nd.val;
}
};
priority_queue<node> pq;
int f(int id, int x){
return x * x * a[id] + x * b[id] + c[id];
}
void init(){
for (int i = 1; i <= n; ++i){
}
for (int i = 1; i <= n; ++i){
if (b[i] % (a[i] + a[i]) == 0){
pq.push(node(f(i, (-b[i]) / (a[i] + a[i])), (-b[i]) / (a[i] + a[i]), i));
}else {
int pos = (-b[i]) / (a[i] + a[i]), pos2;
if (b[i] < 0) pos2 = pos + 1;
else pos2 = pos - 1;
pq.push(node(f(i, pos), pos, i));
pq.push(node(f(i, pos2), pos2, i));
}
}
}
void solve(){
int tot = 0;
while (k--){
node tmp = pq.top();
pq.pop();
ans[++tot] = tmp.val;
int i = tmp.id, x = tmp.x;
if (b[i] % (a[i] + a[i]) == 0 && x == (-b[i]) / (a[i] + a[i])){
pq.push(node(f(i, x - 1), x - 1, i));
pq.push(node(f(i, x + 1), x + 1, i));
}else {
if (x * (a[i] + a[i]) < (-b[i])) pq.push(node(f(i, x - 1), x - 1, i));
else pq.push(node(f(i, x + 1), x + 1, i));
}
}
for (int i = 1; i < tot; ++i)
printf("%d ", ans[i]);
printf("%d\n", ans[tot]);
}
int main(){
init();
solve();
return 0;
}


## Zsi-r's solution

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

class poly
{
friend int cal(const poly &tmp, int x) { return tmp.a * x * x + tmp.b * x + tmp.c; }
public:
int a, b, c;
int minx; //if (minx>0) plus 1 each time;else minus;
bool grater0;
int miny;
poly(){};
poly(int a1,int b1,int c1):a(a1),b(b1),c(c1){
minx = -b / 2 / a;
miny = a * minx * minx + b * minx + c;
if (b<=0)
grater0 = true;
else
grater0 = false;
}
~poly(){};
};

class priorityQueue
{
public:
priorityQueue(){};
priorityQueue(int capacity);
~priorityQueue();
void enQueue(int x);
int deQueue();
private:
int currentSize;
int *array;
int maxSize;

void doubleSpace();
void buildHeap();
void percolateDown(int hole);
};

priorityQueue::priorityQueue(int capacity)
{
array = new int[capacity];
maxSize = capacity;
currentSize = 0;
}

priorityQueue::~priorityQueue()
{
delete[] array;
}

{
return array[1];
}

void priorityQueue::enQueue(int x)
{
if (currentSize == maxSize-1)//因为array[0]不放东西
doubleSpace();

//向上过滤
int hole = ++currentSize;
for (; hole > 1 && x > array[hole / 2]; hole /= 2)
array[hole] = array[hole / 2];
array[hole] = x;
}

int priorityQueue::deQueue()
{
int maxItem;
maxItem = array[1];
array[1] = array[currentSize--];
percolateDown(1);
return maxItem;
}

void priorityQueue:: percolateDown(int hole)//向下过滤
{
int child;
int tmp = array[hole];
for (; hole * 2 <= currentSize; hole = child){
child = hole * 2;
if (child!=currentSize && array[child+1]>array[child])//找大的儿子，如果child==currentSize，则没有右儿子
child++;
if(array[child]>tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}

void priorityQueue::buildHeap()
{
for (int i = currentSize / 2; i > 0;i--)
percolateDown(i);
}

void priorityQueue::doubleSpace()
{
int *tmp = array;
maxSize *= 2;
array = new int[maxSize];
for (int i = 1; i <= currentSize; i++) //当currentSize == maxSize-1时，调用intSpace()
array[i] = tmp[i];
delete[] tmp;
}

int main()
{
int a, b, c;
cin >> n >> k;
bool flag = false;
poly *polyarray = new poly[n];
priorityQueue output(k+1);
for (int i = 0; i < n;i++)
{
cin >> a >> b >> c;
poly tmp(a,b,c);
polyarray[i] = tmp;
}
//初始化
if (n>=k)
for (int i = 0; i < k;i++)
{
output.enQueue(polyarray[i].miny);
}
else
{
flag = true;
for (int i = 0; i < n;i++){
output.enQueue(polyarray[i].miny);
}
count = n+1;
while(true)
{
if (polyarray[0].grater0)
{
if (count > k)
break;
count++;
if (count > k)
{
{
output.deQueue();
count++;
}
break;
}
else{
count++;
}
}
else
{
if (count > k)
break;
count++;
if (count > k)
{
{
output.deQueue();
count++;
}
break;
}
else{
count++;
}

}
}
}
//for (int i = 0; i < k;i++)
//{
//    cout << output.deQueue() << ' ';
//}
for (int i = 0; i < n;i++)
{
bool plus=false;
if (polyarray[i].grater0)
plus = true;
int sumplus,summinus;
int j;
if (i == 0 && flag == true)
{
}
else

for (;;j++)
{
sumplus = cal(polyarray[i], polyarray[i].minx + j);
summinus = cal(polyarray[i], polyarray[i].minx - j);
if (plus)
{
break;
output.deQueue();
output.enQueue(sumplus);
if (j==0)
continue;
break;
output.deQueue();
output.enQueue(summinus);
}
else if(!plus)
{
break;
output.deQueue();
output.enQueue(summinus);
if (j ==0)
continue;
break;
output.deQueue();
output.enQueue(sumplus);
}
}
}
int *outputarray = new int[k];
for (int i = k - 1; i >= 0; i--)
{
outputarray[i] = output.deQueue();
}
for (int i = 0; i < k;i++)
{
cout << outputarray[i] << ' ';
}
delete[] outputarray;
delete[] polyarray;
return 0;
}