题目连接: Managing Difficulties
题目: 略
大致题意:
t组输入, 每组给你n个数字, 问你这n个数字中能找出多少个等差三元组.
解题思路:
假设有下标为 i, j, k(i < j < k)的三个元素满足题意, 那么由等差队列的性质我们可知,2a[j] = a[i] + a[k]
得出a[i] = 2a[j] - a[k]
至此, 我们发现我们只需要不断枚举a[j]和a[k]即可通过公式找出对应的a[i].
最后就涉及到存储数据问题了, 由于数字的范围可达1E9 (实际我发现只有1E6的数据), 如果1E9直接用数组存储是开不下的, 这时就会想到用map存储, 算一下复杂度 大约是n2logn, 是可以接受的.
AC代码:
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN = 2E3 + 10;int a[MAXN]; //存数字map<int, int> m;int main(){int t; scanf("%d", &t);while (t--) {m.clear();int n; scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);int res = 0; m[a[1]] = 1; //中间元素不可能是第一个, 可以直接跳过第一个元素的情况for (int i = 2; i <= n - 1; ++i) {//枚举中间元素a[j]for (int j = i + 1; j <= n; ++j) {//枚举a[k]int ak = 2 * a[i] - a[j]; //求a[i]if (ak < 0 || !m.count(ak)) continue; //m.count()很关键, 此句记为*res += m[ak]; //记录结果}m[a[i]]++; //把a[j]记录为出现过的元素}printf("%d\n", res);}return 0;}
关于这道题, 我看别的大佬用unordered_map做的, 说如果用普通的map会卡时间, 这里来说明一下, 并且解释一下 * 处:
关于map容器的count()函数作用:
可以以复杂度logn来得到当前map容器中是否存在该元素.
此时你可能想问, 如果我直接判断m[index]==0不也可以吗? 但是二者最重要的区别就是, 如果你以后者进行判断, 如果容器中本身没有index元素, 则会添加上index元素, 这样会增大容器的存储数据, 从而导致超时, 而count函数则不会. 因此如果在*处没有用count()函数, 而是直接 进行res+=m[ak]的操作, 虽然结果不会有影响, 但是会大大降低后续容器的查找效率.
关于unordered_map:
对这个题而言, 的确用unordered_map要比普通的map快, 特别是如果也运用了count函数则会更快, 大约快了近一倍(都用count函数的情况下).
