比赛 20111108 评测结果 AAAAAAAAAT
题目名称 数对的个数 最终得分 90
用户昵称 magic 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-11-08 10:22:41
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. const int maxlong=100000000;
  5. int data[200005],ans,n,c;
  6. void qsort(int a[],int l,int r);
  7. void qsort(int a[],int l,int r)
  8. {
  9. int i,j,x,y;
  10. i=l;j=r;x=a[(l+r)/2];
  11. while (i<=j)
  12. {
  13. while (a[i]<x) i++;
  14. while (a[j]>x) j--;
  15. if (i<=j)
  16. {
  17. y=a[i];a[i]=a[j];a[j]=y;
  18. i++;j--;
  19. }
  20. }
  21. if (l<j) qsort(a,l,j);
  22. if (i<r) qsort(a,i,r);
  23. }
  24. int main()
  25. {
  26. freopen("dec.in","r",stdin);
  27. freopen("dec.out","w",stdout);
  28. scanf("%d%d",&n,&c);
  29. for (int i=1;i<=n;i++)
  30. {
  31. scanf("%d",&data[i]);
  32. }
  33. qsort(data,1,n);
  34. int le,ri,mid;
  35. data[n+1]=maxlong;
  36. for (int i=1;i<=n;i++)
  37. {
  38. le=i+1;
  39. ri=n;
  40. while (le<ri)
  41. {
  42. mid=(le+ri)/2;
  43. if (data[mid]-data[i]>=c)
  44. {
  45. ri=mid;
  46. }
  47. else
  48. {
  49. le=mid+1;
  50. }
  51. }
  52. for (int j=le;j<=n;j++)
  53. {
  54. if (data[j]-data[i]==c)
  55. {
  56. ans++;
  57. }
  58. else
  59. {
  60. break;
  61. }
  62. }
  63. }
  64. if (c==0) ans*=2;
  65. printf("%d",ans);
  66. return 0;
  67. }