2348: [Baltic 2011]Plagiarism
Time Limit: 1 Sec Memory Limit: 256 MBSubmit: 501 Solved: 232
[Submit][Status][Discuss]
Description
世界编程大赛的选手们提交
N
份程序文件
f
1
, …, fN
给评测系统。在将评测结果正式公布之前，评委会想要排除一切可能的剽窃现象。他们已有一个对比程序，用来比较两份程序文件，并判断它们是否太过相似了。
然而程序文件的数目相当大，把每两份（一对，
pair
）文件都进行比较的话将花太多的时间。另一方面，许多对
(pair)
可以直接被排除，如果文件的大小相差太大的话。
更准确地说，评委会决定，如果每两份文件（一对，
pair
）中，较小文件的体积小于较大文件的体积的
90%
，那将直接不比较这样的一对
(pair)
。所以，对比程序只比较这样的一对
(fi, fj)
：
i≠j, size(fi )≤ size(fj )
且
size(fi )≥0.9?size(fj )
。
编写程序计算有多少对
(pair)
文件需要被比较。
Input
第
1
行包含一个整数
N
，即提交的程序文件总数。
第
2
行包含
N
个整数
size(f1), …, size(fN)
，每个整数代表文件的体积大小。
Output
第
1
行，也是唯一的一行，给出一个整数，即需要被比较的文件的对
(pair)
的数目。
数据范围
1≤ N ≤100 000
1≤ size(fi ) ≤100 000 000
有50分的测试点中，1≤ N ≤2 000
Sample Input
5
1 1 1 1 1
1 1 1 1 1
Sample Output
10
HINT
第
2
个样例中，每两个文件之间都要互相比较（当然，每对只比较一次，不是两次）。
Source
（原本以为需要二分搞一搞，仔细想想二分都不用，排个序，维护两个指针O（n）扫就好）
思路：将size序列排序，我是从小到大排，保证当前枚举到的size[i]对于任意(j<i)的size[j]，有size[i]>=size[j]，维护另一指针k，使k为size[k]>=size[i]*0.9，则每次将i-k计入答案
附AC代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#define N 1000001
#define ins 1e-8
using namespace std;
typedef long long ll;
ll n,size[N],ans;
int main()
{scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&size[i]);sort(size+1,size+1+n);for(ll i=1,j=1;i<=n;i++){while((long double)(size[j]+ins)<(long double)size[i]*0.9)j++;ans+=i-j;}printf("%lld\n",ans);
}