fork(4) download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<climits>
  5. using namespace std;
  6. int arr[10001];
  7. int a=0,b=0,d=INT_MAX,n,m;
  8. int used[10001];
  9. void bs(int f,int l)
  10. {
  11. int i=f,j=l-1,sum,mid;
  12. sum=m-arr[l];
  13. while(i<=j)
  14. {
  15.  
  16. mid=(i+j)/2;
  17. if(arr[mid]>sum)
  18. j=mid-1;
  19. else if(arr[mid]<sum)
  20. i=mid+1;
  21. else break;
  22. }
  23. if(!used[mid])
  24. {
  25. used[mid]=1;
  26. if(i<=j)
  27. {
  28.  
  29. if((arr[l]-arr[mid])==0)
  30. {
  31. a=arr[mid];
  32. b=arr[l];
  33. return ;
  34. }
  35. if(d>(arr[l]-arr[mid]))
  36. {
  37. d=arr[l]-arr[mid];
  38. a=arr[mid];
  39. b=arr[l];
  40. }
  41. bs(f+1,l-1);
  42. }
  43. else
  44. bs(f,l-1);
  45. }
  46. }
  47. int main()
  48. {
  49. int i;
  50. while(scanf("%d",&n) == 1)
  51. {
  52. for(i=0;i<n;i++)
  53. scanf("%d",&arr[i]);
  54. scanf("%d",&m);
  55. sort(arr,arr+n);
  56. memset(used,0,sizeof(used));
  57.  
  58. a = b = 0;
  59. d = INT_MAX;
  60.  
  61. bs(0,n-1);
  62.  
  63. printf("Peter should buy books whose prices are %d and %d.\n\n",a,b);
  64. }
  65. return 0;
  66. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
2
40 40
80

5
10 2 6 8 4
10

4
4 6 2 8
10

3
1000000 100000 1
1100000
stdout
copy 
Peter should buy books whose prices are 40 and 40.

Peter should buy books whose prices are 0 and 0.

Peter should buy books whose prices are 4 and 6.

Peter should buy books whose prices are 100000 and 1000000.
https://ideone.com/V3DjHt
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!