有点不好做，先得知道二次函数的性质，最小值是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(); } } |