【16届蓝桥杯寒假刷题营】第2期DAY5

5.变变数组 - 蓝桥云课

给定一个长度为 n 的整数数组 A，A 中第 i 个元素为 Ai​（1≤i≤n），你只能在 A 中选择一个元素 a，将 A 中所有数值等于 a 的元素变为 a2，请问变化后 A 中所有元素和的最大为多少。

输入格式

输入共 2 行。

第一行包含一个整数 n，表示整数数组 A 中元素的个数。

第二行包含 n 个整数，表示整数数组 A 中各个元素的值。

输出格式

输出共一行，包含一个整数，表示变换后 A 中所有元素和的最大值。

样例输入

5
-3 1 0 2 2

样例输出

14

评测数据规模

对于所有评测数据，1≤n≤1e5，−1e4≤Ai​≤1e4。

思路如下：
相当于暴力，先计算未被改变的总和，之后再分别计算改变这个数的总和，求出最大。

代码如下：
 

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
ll n; 
ll maxn = -1e9;
ll sum;
int main(void)
{map <int,int> mp;cin >> n;for(ll i = 1 ; i <= n ; i++){ll x;cin >> x;mp[x]++;sum += x;//先计算未改变的总和 }for(auto it = mp.begin() ; it != mp.end() ; it++) {ll key = it->first;ll num = it->second; maxn = max(maxn,sum - num*key + num*key*key);}cout << maxn;return 0;
}