2019 CCPC女生赛 Function

2019 CCPC女生赛 Function
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

13

Source

2019中国大学生程序设计竞赛-女生专场

 思路
1. ```
由 n == m 得  
所有的  x=1  得总值   
1
2
```
2. ```
如果 n
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11

代码

#include "bits/stdc++.h"
using namespace std;
#define ll long long 
struct ppp
{
	ll a,b,c,x;
	ll ans;
	bool operator <(const ppp &x) const
	{
		if(ans==x.ans)
			return a>x.a;
		return ans>x.ans;
	}
	
}t;
priority_queue<ppp>q;
int main()
{
	ll n,m;
	ll sum=0;//记录总值
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		t.x=1;//一开始所有的x=1
		cin>>t.a>>t.b>>t.c;
		sum+=t.a+t.b+t.c;//x=1的结果
		t.ans=(2*t.x+1)*t.a+t.b; //x 与 x+1 的差值 (2x+1)a+b 
		q.push(t);
	}
	m-=n;
	while(m--)
	{
		t=q.top();
		q.pop();
		t.x++;
		sum+=t.ans;//加上差值
		t.ans=(2*t.x+1)*t.a+t.b; 
		q.push(t);
	}
	cout<<sum<<endl;
}
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

Problem Description

Input

Output

Sample Input

Sample Output

Source

思路

代码