Skip to content

14252: 【原4252】函数值

题目

题目描述

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

函数值

题目描述

有\(n\)个开口向上的二次函数\(f_i(x) = a_ix^2 + b_ix + c_i\)
我们现在只考虑\(x\)是整数的情况，对于每个整数\(x\)用这\(n\)个函数作用之都能得到\(n\)个数，即使数值相同我们也认为是重复的多个
将\(x\)取遍所有整数，在得到的无穷多个数中，求最小的\(k\)个数并从小到大输出

输入格式

第一行两个数\(n, k\)，表示序列长度和所求数个数
接下来\(n\)行，每行三个数\(a_i, b_i, c_i\)，表示函数\(f_i(x)\)

输出格式

一行\(k\)个数表示最小的\(k\)个数

样例输入1

2 9
1 0 0
1 2 0

样例输出1

-1 0 0 0 1 1 3 3 4

数据规模

对于100%的数据有
\(0 < a_i\)
对于30%的数据有
\(b_i \% (2 * a_i) = 0\)
对于60%的数据有
\(b_i \% a_i = 0\)
对于40%的数据有
\(n \leq 500\)
\(k \leq 500\)
对于70%的数据有
\(n \leq 3000\)
\(k \leq 3000\)
对于100%的数据有
\(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 read(){
    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(){
    n = read(), k = read();
    for (int i = 1; i <= n; ++i){
        a[i] = read(), b[i] = read(), c[i] = read();
    }
    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;
    bool haveaddfirst = false;
    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();
    int getHead() const;
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;
}

int priorityQueue::getHead() const
{
    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;
    int n, k,count,countforadd;
    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++)
        {
            polyarray[i].haveaddfirst = true;
            output.enQueue(polyarray[i].miny);
        }
    else
        {
            flag = true;
            for (int i = 0; i < n;i++){
                output.enQueue(polyarray[i].miny);
                polyarray[i].haveaddfirst = true; 
            }
            count = n+1;
            countforadd = count;
            while(true)
            {
                if (polyarray[0].grater0)
                {
                    if (count > k)
                        break;
                    output.enQueue(cal(polyarray[0], polyarray[0].minx + (countforadd-n)));
                    count++;
                    if (count > k)
                    {   
                        if (cal(polyarray[0], polyarray[0].minx - (countforadd-n))<output.getHead())
                        {
                            output.deQueue();
                            output.enQueue(cal(polyarray[0], polyarray[0].minx - (countforadd-n)));
                            countforadd++;
                            count++;
                        }
                        break;
                    }
                    else{
                        output.enQueue(cal(polyarray[0], polyarray[0].minx - (countforadd-n)));
                        count++;
                        countforadd++;
                    }
                }
                else
                {
                    if (count > k)
                        break;
                    output.enQueue(cal(polyarray[0], polyarray[0].minx - (countforadd-n)));
                    count++;
                    if (count > k)
                    {   
                        if (cal(polyarray[0], polyarray[0].minx + (countforadd-n))<output.getHead())
                        {
                            output.deQueue();
                            output.enQueue(cal(polyarray[0], polyarray[0].minx + (countforadd-n)));
                            count++;
                            countforadd++;
                        }
                        break;
                    }
                    else{
                        output.enQueue(cal(polyarray[0], polyarray[0].minx + (countforadd-n)));
                        count++;
                        countforadd++;
                    }

                }
            }
        }
    //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)
        {
            j = countforadd - n;
        }
        else
            j = polyarray[i].haveaddfirst;

        for (;;j++)
        {
            sumplus = cal(polyarray[i], polyarray[i].minx + j);
            summinus = cal(polyarray[i], polyarray[i].minx - j);
            if (plus)
            {   
                if (sumplus>output.getHead())
                    break;
                output.deQueue();
                output.enQueue(sumplus);
                if (j==0)
                    continue;
                if (summinus>output.getHead())
                    break;
                output.deQueue();
                output.enQueue(summinus);
            }
            else if(!plus)
            {   
                if (summinus>output.getHead())
                    break;
                output.deQueue();
                output.enQueue(summinus);
                if (j ==0)
                    continue;
                if (sumplus>output.getHead())
                    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;
}