[C++知识库]c++ map 与unordered_map 与set 的比较

map：红黑树，查找速度O（log n）稳定 且足够快，有序，
unordered_map:哈希散列表 ，查找速度O（1~M）M为key值长度，由于无序哈希map 的查找速度并不稳定，且空间复杂度更大
所以哈希map不一定比map 好用，有时候需要仔细了解，其实log n 比1也就二大了最多几十倍，哈希map比map快l 那么一点但是如果key值（string类型）过长，有时候就会比map慢很多。
set与unordered_set类比于map与哈希map ，原理相同，但我更倾向用map因为之前碰到一题被set卡了。
接下来讲下今天我wa无数次的题：
关于遍历一个使用for（auto pr ：s）,而不是去从0开始一直遍历到结束，因为我发现第二种做法浪费时间的同时 空间复杂度巨大，可能是因为一些我没有赋值的key在我一个个遍历时占用了无效的空间。相当于我对我最大开了2e9的空间大小的红黑树。

Educational Codeforces Round 115 (Rated for Div. 2)

C. Delete Two Elements

Monocarp 有一个由 n 个整数组成的数组 a。让我们将 k 表示为这些元素的数学平均值（请注意，k 可能不是整数）。

n 个元素的数组的数学平均值是元素的总和除以这些元素的数量（即总和除以 n）。

Monocarp 想要从 a 中删除两个元素，以便剩余 (n-2) 个元素的数学平均值仍然等于 k。

您的任务是计算位置 [i,j] (i<j) 对的数量，如果删除这些位置上的元素，则剩余 (n-2) 个元素的数学平均值等于 k（即，它等于原始数组 a) 的 n 个元素的数学平均值。

输入
第一行包含一个整数 t (1≤t≤104)——测试用例的数量。

每个测试用例的第一行包含一个整数 n (3≤n≤2?105)——数组中元素的数量。

第二行包含一个整数序列 a1,a2,…,an (0≤ai≤109)，其中 ai 是数组的第 i 个元素。

所有测试用例的 n 总和不超过 2?105。

输出
打印一个整数 — 位置对的数量 [i,j] (i<j) 使得如果删除这些位置上的元素，则剩余 (n-2) 个元素的数学平均值等于 k（即，它等于原始数组 a) 的 n 个元素的数学平均值。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>
#define ll long long 

using namespace std;
const int N = 2e5+5;
int t,n,a;
ll sum,ans;
int main()
{
  scanf("%d",&t);
  while(t--)
  {
      map<int,int>s;
      s.clear();
      sum=0,ans=0;
      scanf("%d",&n);
      for(int i=0;i<n;i++)
      {
          scanf("%d",&a);
          sum+=a;
          s[a]++;
      }
      double avg=1.0*sum/n;
      ll k=avg*2;
      if(k==2*avg)
      {
          ll d=0,ret=0;
       for(auto pr :s)
       {
           int x=pr.first;
           int y=pr.second;
           if(k==2*x)d+=(ll)y*(y-1)/2;
           else ret+=(ll)y*s[k-x];
       }
       printf("%lld\n",ret/2+d);
      }
      else 
      {
          puts("0");
      }
      
  }
  return 0;
}