蛋糕店 题解

题目

最近小 $G$ 新开了一家蛋糕店。开业第一天，一共来个 $n$ 位顾客。由于小 $G$
非常懒，他每次只会接待一位顾客。每个顾客都想尽快的买到蛋糕，所以没有第
一个买到蛋糕的顾客都会有一个愤怒值。最终排在第 $i$ 个位置的顾客 $x$ 的愤怒值
为 $i$*$a$[$x$]。小 $G$ 想要所有顾客的愤怒值之和最小。求最小的愤怒值之和。

---

输入

第一行为一个整数 $n$，表示顾客数。
第二行输入 $n$ 个整数 $a$[1]…$a$[$n$] ，含义见题面

---

输出

一行一个整数 $ans$，表示最小的愤怒值之和。

---

样例

input
5
8 5 8 4 6

output
51

explain
Ans=81+62+53+44=51

---

数据范围

对于 30%的数据，1 ≤ $n$ ≤ 10。
对于 60%的数据，1 ≤ $n$ ≤ 1000。
对于 100%的数据，1 ≤ $n$ ≤ 1000000。

---

解题思路

排个序
相乘再相加就好
我nc用了高精

---

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,b[30],f[50],l,t;
long long a[1000010];
void xj()
{int w=0;t=max(l,t);for (int i=1;i<=t;i++){f[i]=f[i]+b[i]+w;w=f[i]/10;f[i]=f[i]%10;}if (w>0)f[++t]=w;
}
int main()
{freopen("cake.in","r",stdin);freopen("cake.out","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+n+1);for (int i=n-1;i>0;i--){ memset(b,0,sizeof(b));long long d=a[i];l=1;while (d>0){b[l]=b[l]+d%10*(n-i);b[l+1]=b[l]/10;b[l]=b[l]%10;l++;d=d/10;}if (b[l]==0)l--; xj();}for (int i=t;i>0;i--)printf("%d",f[i]);fclose(stdin);fclose(stdout);return 0;
}