我要评论HDU6546_Function
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
思路分析：
对于n个方程:
-
条件：
想得到n个正整数x使得x之和为m，且方程所得值的和最小。 -
思路：
由于正整数，所以刚开始先每个都分配1。
然后接下来由于：
所以这就是在给一个x分配1后ans增加的值，想让这个值尽可能小，所以需要用优先队列维护这个增值即可。
- 以 1 为出发点，将所有 F(X)中的X设为 1 然后根据 F(x+1)-F(x)的差值来决定最小的贪心。
- 维护 [ F(x+1)-F(x) ]差值的变化，并且选择最小的；
- 第二轮循环，因为n<=m所以在初始 X=1 之后还剩可分配的点数 就只有（M-N）了；
代码：
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <stack>
#include <algorithm>
#include <queue>
#include <set>
#include <cstdio>
#define INF 0x3f3f3f3f
#define MAX 200100
#define ll long long
#define N 10010
using namespace std;
//一看IO流就是我做的！
int n,m;
ll ans=0;
//全局变量用时少！
struct Node{
ll a,b,c;
ll yqx,x;
bool operator<(const Node &t)const{
return yqx>t.yqx;
}
};
priority_queue <Node,vector<Node>,less<Node>>wyy;
//升序排列的优先队列
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++){
Node temp;
temp.x=1;
cin>>temp.a>>temp.b>>temp.c;
temp.yqx=temp.a*(2*temp.x+1)+temp.b;
wyy.push(temp);
ans+=temp.a+temp.b+temp.c;
}
for(int i=0;i<m-n;i++){
Node sn;
sn=wyy.top();
wyy.pop();
ans+=sn.yqx;
sn.x++;
sn.yqx=(sn.a)*(2*sn.x+1)+sn.b;
wyy.push(sn);
}
cout<<ans<<endl;
}
复习一下优先队列
本文地址：https://blog.csdn.net/weixin_45849398/article/details/109007938
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论