洛谷 P2085 最小函数值

有点不好做,先得知道二次函数的性质,最小值是x=-b/2a。然后用堆的时候要小心,要用大根堆,一次性把堆加满,探测每个二次函数轴附近的值是否比堆里的最大值大,如果是的话就把堆里的最大值取出来,不是的话就可以终止这次二次函数的循环了。最后因为是大根堆,用个栈把顺序颠倒过来再输出就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, m;
int A[10005], B[10005], C[10005];
priority_queue<int> pq;
stack<int> s;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)pq.push(0x7fffffff);
    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i] >> C[i];
        double pivot = -1.0*B[i] / 2 / A[i];
        if (pivot < 0) {
            for (int j = 1; j <= m; j++) {
                int v = A[i] * j*j + B[i] * j + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else break;
            }
        }
        else {
            int p = round(pivot);
            int v = A[i] * p * p + B[i] * p + C[i];
            if (v < pq.top()) {
                pq.pop();
                pq.push(v);
            }
            for (int j = 0; 2 * j <= m - 1; j++) {
                bool flag = true;
                v = A[i] * (p + j + 1)*(p + j + 1) + B[i] * (p + j + 1) + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else flag = false;
                v = A[i] * (p - j - 1)*(p - j - 1) + B[i] * (p - j - 1) + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else flag = false;
                if (!flag)break;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        s.push(pq.top());
        pq.pop();
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注