蓝桥杯算法提高-能量项链-题解（C++代码）

解题思路:
    要得到最大值，每次聚合时把小的数消掉，这样后面聚合得到的值就会越大，如（5，3）（3，2）（2，10）（10，5）这样的一个序列

其中2最小首先把2消去， 即 （3，2）和（2，10）聚合 得到值 sum = 60，得新组合（3，10）；

剩下 （5，3）（3，10）（10，5）

其中3最小我们消去3，得sum = 60 + 150 = 210；

最后（10，5）（5，10） 得 sum = 60 + 150 + 500 = 710；

参考代码:

#include #include using namespace std;
int arr[105];
const int inf = 1005; // 最大数为1005

int main(){
	int n, x, sum = 0;
	map mp;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 0; i < n; i++) { 
		if (i == n - 1) mp[arr[i]] = arr[0];
		else mp[arr[i]] = arr[i + 1];
	}
	
	for (int i = 0; i < n-1; i++) {
		int Min = inf, index = 0;
		for (map::iterator it = mp.begin(); it != mp.end(); ++it) {//找到最小数
			if (Min > (*it).second) Min = (*it).second, index = (*it).first;
		}
		sum += index * Min * mp[Min];
		mp[index] = mp[Min]; //聚合成新的组合
		mp[Min] = inf;//把最小数所对应的值改为inf，不再考虑这个组合
	}
	cout << sum << endl;

	return 0;
}