题目描述
牛牛和牛妹喜欢玩平板游戏,游戏一开始屏幕上会出现很多个图形,玩家在每一轮可以合并两个图形,当只有一个图形的时候游戏结束,每个图形都有一个大小,合并完成后的图形的大小为x+y,x和y分别为合并之前的两个图形,与此同时,玩家会获得x*y的分数。
牛牛和牛妹新开了一盘游戏,屏幕上出现了n个图形,每个图形的大小已知,请算出牛牛和牛妹最大能获得的分数
题目分析:
这是一道难得的水题,只要一次sort排序,在从小到大按照题目依此进行计算就可以了。
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int main () { int n; int a[105]; cin >> n; for (int i=1;i<=n;i++) { cin >> a[i]; } sort(a+1,a+1+n); int sum=0; for (int i=2;i<=n;i++) { sum=sum+a[i]*a[i-1]; a[i]=a[i]+a[i-1]; } cout << sum << endl; return 0; }