题解 | 数组重乘法 数学规律&贪心

#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <string>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <cstring>
#define ll long long
const ll N = 2e5 + 10;
const ll Max = 1e18 + 10;
const ll MOD = 998244353;
using namespace std;

ll saki[N];
ll soyo[N];

int main() {

	ll t;
	cin >> t;

	while (t--) {
		ll n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> saki[i];
		}

		sort(saki + 1, saki + 1 + n);

		ll l = 1, r = n;
		ll i = 1;
		while (l <= r) {
			if (l == r) {
				soyo[l] = saki[i++];
				break;
			}
			soyo[r--] = saki[i++];
			soyo[l++] = saki[i++];
		}

		ll sum = 0;
		for (int i = 1; i < n; i++) {
			sum += soyo[i] * soyo[i + 1];
		}
		cout << sum << '\n';

	}

	return 0;
}

蒟蒻在考场上的时候模拟了几组数据发现了一个规律就是第一小的放最后的位置，第二小的放第一个位置，第三小的放倒数第二个位置，以此类推，到最后大的在中间，这样算出来的答案就是最优的，要注意一下奇偶数的处理