Function （思维+优先队列）

Function

 解题思路：

因为 x 是正整数，所以每个 Fi 都必须先分配 xi=1。这时候还剩下 m-n 个 1 没有分配，采用贪心原则。首先需要先知道对于每一次分配的1，产生的增量为：

 所以我们每次都取最小的增量，最后即为最小的增量。这就用到了优先队列

AC_Code:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <cmath>
 7 typedef long long ll;
 8 using namespace std;
 9 const int maxn = 1e5+5;
10
11 ll n,m,a[maxn],b[maxn],c[maxn];
12 struct node{
13     ll id,val;
14     bool operator < (const node &r) const{
15         return r.val<val;
16     }
17 }tmp;
18 priority_queue<node>que;
19 ll x[maxn];
20
21 int main()
22 {
23     while( ~scanf("%lld%lld",&n,&m)){
24         while( !que.empty() ) que.pop();
25         ll ans=0;
26         for(int i=1;i<=n;i++){
27             scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
28             tmp.id = i;
29             tmp.val = 2ll*a[i]*1ll+a[i]+b[i];
30             x[i] = 1;
31             que.push(tmp);
32             ans += a[i]+b[i]+c[i];
33         }
34         ll num = m-n;
35         while( num ){
36             num--;
37             int id = que.top().id;
38             x[id]++;
39             ans += que.top().val;
40             tmp.id = id;
41             tmp.val = 2*a[id]*x[id]+a[id]+b[id];
42             que.pop();
43             que.push(tmp);
44         }
45         printf("%lld\n",ans);
46     }
47     return 0;
48 }