会员专享
请先
登录,登录后可使用今日免费解锁;
开通会员后可解锁完整内容。
二重循环枚举朴素解法
这道题的正解是 树状数组,但是我们用朴素解法 二重循环枚举 也能在考试时拿到一定的分数。
题意:给定数组 record 和阈值 threshold,统计满足 i<j 且 record[i]−record[j]>threshold 的下标对个数(严重性能逆序对)。
朴素做法:两重循环枚举所有 0≤i<j<n,若 record[i]−record[j]>threshold,答案加 1。
小数据可以过;当 n 达到 105 时,O(n2) 会超时,需要后面的树状数组做法。