本文共 1175 字，大约阅读时间需要 3 分钟。

注意题目中的绝对值

描述

给定一个长度为 n 的数组，定义数组的贡献值为数组中 每个数首次出现的位置 * 每个数出现的次数 之和（相同的数字只计算一次）。

例如：1 2 2 3 1，数字 1 首次出现的位置是 1，总共出现了 2 次，所以提供 1 * 2 = 2 的贡献值，数字 2 是 2 * 2 = 4，数字 3 是 4 * 1 = 4，因此这个数组的贡献值为 2 + 4 + 4 = 10。

但很显然这样是难不倒罗少的，所以附加了一个条件，你可以任意改变数组中数的位置，问改变后数组最大的贡献值是多少？

输入

每组案例包含一个正整数 n ，代表数组的长度。(1 <= n <= 100000)

然后是 n 个整数 ai。(|ai| <= 10000)注意

输出

样例输入

样例输出

HINT

对于样例1：1 2 1 2

改变前数组的贡献值为 1 * 2 + 2 * 2 = 6

你可以把他改为 1 1 2 2 或者 2 2 1 1 得到更大的数组的贡献值 8。

#include
   
    #include
    
     using namespace std;bool cmp(int a, int b){
   	return a > b;}int main(){
   	int t;	cin >> t;	while (t--)	{
   		int n;		cin >> n;		int a[20002] = {
    0 };		for (int i = 1; i <= n; i++)		{
   			int x;			cin >> x;			a[x+10000]++;//		}		sort(a, a + 20002,cmp);//快排		int p = n;		long long int sum = 0;		int flag = false;		int j = 0;		while (p > 1)		{
   			if (!flag)			{
   				p = p - a[j]+1;				sum = sum + p * a[j];				flag = true;			}			else			{
   				p = p - a[j];				sum = sum + p * a[j];			}			j++;		}		cout << sum << endl;	}}
    
   

转载地址：https://blog.csdn.net/YYDS777/article/details/114491543 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！