2019CCPC 女生赛C 二次函数思维（水？）题（贪心）_综合

2019CCPC 女生赛C 二次函数思维（水？）题（贪心）

题目：
Function
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description
wls 有 n 个二次函数 Fi(x) = aix2 + bix + ci (1 ≤ i ≤ n).
现在他想在∑ni=1xi = m 且 x 为正整数的条件下求∑ni=1Fi(xi)的最小值。
请求出这个最小值。

Input
第一行两个正整数 n, m。
下面 n 行，每行三个整数 a, b, c 分别代表二次函数的二次项，一次项，常数项系数。
1 ≤ n ≤ m ≤ 100, 000
1 ≤ a ≤ 1, 000
?1, 000 ≤ b, c ≤ 1, 000

Output
一行一个整数表示答案。

Sample Input

2 3
1 1 1
2 2 2

Sample Output

根据题意，因为每个 $x_{i}$ 都是正整数，且 $n < m$ ,所以很自然的想到，将 $x_{i}$ 先赋一个1，存入ans中。那么接下来，我们应该维护一个 $x_{i}$ 从1~2的增量。每次挑选这个增量最小的，加到ans中，在把该增量的下一个增量放进去。这个思路很明显了，用优先队列去维护即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
const int N = 100007;
const int mod = 1000000007;
const double pi = acos(-1);
const double db = 1;
const int INF = 0x3f3f3f3f;
#define endl '\n';
const double EPS = 1e-6;
LL read()
{
    LL x = 0, w = 1;char ch = 0;while (ch < '0' || ch>'9'){
    if (ch == '-'){
    w = -1;}ch = getchar();}while (ch >= '0' && ch <= '9'){
    x = x * 10 + ch - '0';ch = getchar();}return w * x;
}struct nod
{
    LL a, b, c;
}F[N];
struct vv
{
    int id;LL x, val;bool operator < (const vv& b)const{
    return val > b.val;}
};
LL solve(int i,LL x)
{
    LL ans = F[i].a * x * x + F[i].b * x + F[i].c;return ans;
}
priority_queue < vv > q;
int main()
{
    std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);LL n, m;cin >> n >> m;LL ans = 0;for (int i = 1; i <= n; ++i){
    int a, b, c;cin >> a >> b >> c;F[i].a = a;F[i].b = b;F[i].c = c;vv tmp;tmp.id = i;tmp.x = 1;tmp.val = solve(i, 1);ans += tmp.val;tmp.x = 2;tmp.val = solve(i, 2) - solve(i, 1);q.push(tmp);}m -= n;for (int i = 1; i <= m; ++i){
    vv tmp = q.top();q.pop();ans += tmp.val;tmp.val = solve(tmp.id, tmp.x + 1) - solve(tmp.id, tmp.x);tmp.x++;q.push(tmp);}cout << ans << endl;return 0;
}