Niuniu looks at the cloud (greedy, hash, push formula) - the first session of Niuke winter vacation training camp

Original link

subject

Ideas

1. The most important point of this question is to pay attention to the observed data range , It shows that there must be a number of repeated occurrences
2. Consider hash , Record the number of occurrences of each number
3. For two different numbers , They can form a total of according to the requirements of the topic $cn{t}_a\ast cn{t}_b$ Same combination
4. For two identical numbers , They can form a total of according to the requirements of the topic $(1+cn{t}_a)\ast cn{t}_a/2$ Same combination 【 Refer to the prime minister's formula with the final term 】.
5. Pay attention $longlong$

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    
	int n;
	cin >> n;
	map<int, int> ma;
	for (int i = 1; i <= n; i ++ )
	{
    
		int x;
		cin >> x;
		ma[x] ++;
	}
	int sum = 0;
	for (int i = 0; i <= 1000; i ++ )
	{
    
		for (int j = i; j <= 1000; j ++ ) 
		{
    
			int add;
			if (i == j) add = (1 + ma[i]) * ma[i] / 2;
			else add = ma[i] * ma[j];
			sum += abs(i + j - 1000) * add;
		}
	}
	cout << sum << endl;
	return 0;
}

summary

During the game, I actually thought about the data range , But then I thought of using set do , In short, it's just another detour , You still need to pay attention to your mentality during the game , Otherwise, you can't do simple problems .

Post a race time error code

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    
    set<int> s;
    unordered_map<int, int> ma;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
    
        int x;
        cin >> x;
        ma[x] ++;
        s.insert(x);
    }
    int sum = 0;
    for (auto i : s)
    {
    
        for (int j : s)
        {
    
            if (i == j)
            {
    
                sum = sum + abs(i + j - 1000) * (ma[i] * (ma[i] - 1));
            }
            else
            {
    
                sum = sum + abs(i + j - 1000) * (ma[i] * ma[j] );
            }
        }
    }
    cout << sum << endl;
    return 0;
}