fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. 	long long int n;
  5. 	long long int a[200005];
  6. 	long long f(long long b)
  7. 	{
  8. 		long long int s=0;
  9. 		for(int i=0;i<n;i++)
  10. 		{
  11. 			s+= abs(a[i]-(b+i+1));
  12. 		}
  13. 		return s;
  14. 	}
  15. int main()
  16. {
  17. 	ios_base::sync_with_stdio(false);
  18.     cin.tie(NULL);
  19. 	cout.tie(NULL);
  20.  
  21. 	cin>>n;
  22.  
  23. 	for(int i=0;i<n;i++)
  24. 	{
  25. 		cin>>a[i];
  26. 	}
  27. 	long long l=-1000000000,r=1000000000,m,res,v1,v2,v3;
  28. 	while(l<=r)
  29. 	{
  30. 		m= (l+r)/2;
  31. 		v1 = f(m-1);
  32. 		v2= f(m);
  33. 		v3 = f(m+1);
  34. 		if(v2<=v1 && v2<=v3)
  35.             {
  36.                 res = m;
  37.                 r=m-1;
  38.             }
  39.             if(v2<=v1 && v3<=v2)
  40.             {
  41.                 l=m+1;
  42.             }
  43.             else
  44.             if(v1<=v2 && v2<=v3)
  45.             {
  46.                 r=m-1;
  47.             }
  48. 	}
  49.  
  50. 	cout<<f(res)<<endl;
  51.     return 0;
  52. }
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Lk4Tm8
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!