「BalticOI 2011 Day2」剽窃 Plagiarism 题解

题目分析

我们需要统计满足以下条件的数对 $(i, j)$ 的数量：

• $1 \le i < j \le N$
• $0.9 \times f_j \le f_i \le f_j$

关键观察

1. 排序简化问题：如果先将数组排序，那么对于任意 $i < j$，都有 $f_i \le f_j$ 自动满足。这样我们只需要关心 $f_i \ge 0.9 \times f_j$ 这个条件。

2. 避免浮点数运算：为了避免浮点数精度问题，可以将所有数乘以 $10$，这样条件变为：

   $$9 \times f_j \le 10 \times f_i \le 10 \times f_j$$

代码解析

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100010;

int n;
LL ans;
int a[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    // 读取数据并乘以10，避免浮点数运算
    for (int i = 1; i <= n; ++i) cin >> a[i], a[i] *= 10;
    
    // 排序数组
    sort(a + 1, a + n + 1);
    
    // 统计满足条件的数对
    for (int i = 1; i <= n; ++i) {
        // 找到第一个满足 a[pos] >= 0.9 * a[i] 的位置
        // 由于都乘以了10，条件变为：a[pos] >= a[i] / 10 * 9
        int pos = lower_bound(a + 1, a + n + 1, a[i] / 10 * 9) - a;
        // i - pos 就是满足 j < i 且 a[j] >= 0.9 * a[i] 的 j 的数量
        ans += i - pos;
    }
    
    cout << ans << '\n';
    return 0;
}

算法思路详解

步骤1：数据预处理

for (int i = 1; i <= n; ++i) cin >> a[i], a[i] *= 10;

将所有数乘以 $10$，这样：

• 原条件：$f_i \ge 0.9 \times f_j$
• 新条件：$10 \times f_i \ge 9 \times f_j$

步骤2：排序数组

sort(a + 1, a + n + 1);

排序后，对于任意 $i < j$，都有 $a_i \le a_j$ 成立。

步骤3：统计有效数对

for (int i = 1; i <= n; ++i) {
    int pos = lower_bound(a + 1, a + n + 1, a[i] / 10 * 9) - a;
    ans += i - pos;
}

对于每个位置 $i$：

• 使用 lower_bound 找到第一个满足 $a_j \ge 0.9 \times a_i$ 的位置 $pos$
• 由于数组已排序，位置 $pos$ 到 $i-1$ 的所有元素都满足：$$0.9 \times a_i \le a_j \le a_i \quad (\text{其中 } j < i) $$
• 因此满足条件的数对数量为 $i - pos$

时间复杂度分析

• 排序：$O(N \log N)$
• $N$ 次二分查找：$O(N \log N)$
• 总时间复杂度：$O(N \log N)$
• 空间复杂度：$O(N)$

示例验证

样例1

输入：
2
2 1

处理过程：
原始数据：[2, 1] → 乘以10后：[20, 10] → 排序后：[10, 20]
i=1: a[1]=10, 0.9*a[1]=9, lower_bound找到pos=1, ans += 1-1=0
i=2: a[2]=20, 0.9*a[2]=18, lower_bound找到pos=2, ans += 2-2=0
输出：0

样例2

输入：
5
1 1 1 1 1

处理过程：
原始数据：[1,1,1,1,1] → 乘以10后：[10,10,10,10,10] → 排序后：[10,10,10,10,10]
i=1: 0.9*10=9, pos=1, ans += 0
i=2: pos=1, ans += 1
i=3: pos=1, ans += 2  
i=4: pos=1, ans += 3
i=5: pos=1, ans += 4
输出：0+1+2+3+4=10

总结

本题通过排序 + 二分查找的方法，将原本需要 $O(N^2)$ 时间复杂度的暴力枚举优化到 $O(N \log N)$，关键技巧包括：

$1$. 排序简化比较条件

$2$. 整数运算避免浮点精度问题

$3$. 利用二分查找快速统计满足条件的数对