修 KaTex
查看原帖
修 KaTex
814343
bc2_cryeggy楼主2024/9/1 18:09
世界编程大赛的选手们提交 $N$ 份程序文件 $f_1, \cdots, f_N$ 给评测系统。在将评测结果正式公布之前,评委会想要排除一切可能的剽窃现象。他们已有一个对比程序,用来比较两份程序文件,并判断它们是否太过相似了。 然而程序文件的数目相当大,把每两份文件都进行比较的话将花太多的时间。另一方面,许多对可以直接被排除,如果文件的大小相差太大的话。 更准确地说,评委会决定,如果每两份文件中,较小文件的体积小于较大文件的体积的 $90\%$,那将直接不比较这样的一对。所以,对比程序只比较这样的一对 $(f_i, f_j)$:$i \neq j$ 且 $\text{size}(f_i) \le \text{size}(f_j)$ 且 $\text{size}(f_i) \ge 0.9 \cdot \text{size}(f_j)$。 编写程序计算有多少对文件需要被比较。

**输入格式:**

第一行包含一个整数 $N$,即提交的程序文件总数。

第二行包含 $N$ 个整数 $\text{size}(f_1), \cdots, \text{size}(f_N)$,每个整数代表文件的体积大小。

**输出格式:**

一行,给出一个整数,即需要被比较的文件的对的数目。

世界编程大赛的选手们提交 NN 份程序文件 f1,⋯ ,fNf_1, \cdots, f_N 给评测系统。在将评测结果正式公布之前,评委会想要排除一切可能的剽窃现象。他们已有一个对比程序,用来比较两份程序文件,并判断它们是否太过相似了。 然而程序文件的数目相当大,把每两份文件都进行比较的话将花太多的时间。另一方面,许多对可以直接被排除,如果文件的大小相差太大的话。 更准确地说,评委会决定,如果每两份文件中,较小文件的体积小于较大文件的体积的 90%90\%,那将直接不比较这样的一对。所以,对比程序只比较这样的一对 (fi,fj)(f_i, f_j):i≠ji \neq j 且 size(fi)≤size(fj)\text{size}(f_i) \le \text{size}(f_j) 且 size(fi)≥0.9⋅size(fj)\text{size}(f_i) \ge 0.9 \cdot \text{size}(f_j)。 编写程序计算有多少对文件需要被比较。

输入格式:

第一行包含一个整数 NN,即提交的程序文件总数。

第二行包含 NN 个整数 size(f1),⋯ ,size(fN)\text{size}(f_1), \cdots, \text{size}(f_N),每个整数代表文件的体积大小。

输出格式:

一行,给出一个整数,即需要被比较的文件的对的数目。

2024/9/1 18:09
加载中...