云计算

题目描述 

计算科学正在经历一场革命,被称为「云计算」,是在互联网上访问软件应用程序、处理能力和数据存储的地方。 在过去的几十年里,计算科学可能已经与我们的工作和家庭生活密切相关。 然而,即使互联网被大量使用,几乎所有的计算资源都是本地的。 这意味着计算机应用、数据存储和处理能力已经接近或相对接近它们的用户。

技术产业革命的春风也吹到了广西大学,我们的创新创业项目渐渐有了拥抱云计算的意识,各大ECS厂商1元/月的学生机被团队们广泛采购并商业化使用,这就是一个很好的栗子。

我们都知道,云计算是将计算运行在别的地方,正如我们接下来的问题需要将困难的问题转移到让聪明的你来解决一样。

现在有nn个三元组(a,b,c)(a,b,c),你需要将他们以任意顺序安排在一个一维数组里,假设数组下标以11开始,对于一个你安排好之后的数列,我们定义他的价值是:
\sum ^{n}_{i=1}[ a_i(i+1) +b_i(n-i)+c_i(i+2)]i=1n?[ai?(i+1)+bi?(ni)+ci?(i+2)]
请问这个数列所有可能中,他最小价值应该是多少?

输入描述:

第一行输入一个整数n表示三元组个数

接下来nn行,每行三个空格分隔的正整数分别表示这个三元组的(a,b,c)(a,b,c)
 
1 \leq n \leq 10^51n105
 
1 \leq a,b,c \leq 1001a,b,c100

输出描述:

输出一行一个整数表示答案
示例1

输入

2 2
4 3
1 3

输出

65

说明

样例的最小价值方案可以是:
[(6,1,3), (3,2,2),(2,4,3)][(6,1,3),(3,2,2),(2,4,3)]
题解:
化简上述式子,然后,就大胆写了一下贪心,没想到就过了,可惜比赛时没敢交呀,话说后台数据是不是有点水呀?
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n;
ll sum;
struct node{
    int a;
    int b;
    int c;
    int bj;
}p[100010];
bool cmp(node x,node y){
    return x.bj>y.bj;
}
ll fc(int a,int b,int c,int i){
    return (a-b+c)*i+a+n*b+2*c;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].a>>p[i].b>>p[i].c;
        p[i].bj=p[i].a-p[i].b+p[i].c;
    }
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)
        sum+=fc(p[i].a,p[i].b,p[i].c,i);
    cout<<sum<<endl;
    return 0;
}

相关推荐