fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. int fun(int n, vector<int>&p) {
  5. 	int sum=0;
  6. 	for(int i=0; i<n; i++) {
  7. 		sum+=p[i];
  8. 	}
  9. 	int temp=sum/n;
  10. 	queue<pair<int,int>>q;
  11. 	int s=true;
  12. 	int cost=0;
  13. 	for(int i=0; i<n; i++) {
  14.  
  15. 		if(p[i]>temp) {
  16. 			q.push({p[i]-temp,i});
  17. 		}
  18. 		else if(p[i]<temp && !q.empty()) {
  19. 			while(!q.empty() && p[i]!=temp) {
  20. 				auto a=q.front();
  21. 				q.pop();
  22. 				if(temp-p[i]<a.first) {
  23. 					a.first-=(temp-p[i]);
  24. 					if(s)
  25. 					{
  26. 						cost+=(temp-p[i])*(i-a.second);
  27. 					}
  28. 					else {
  29. 						cost+=(temp-p[i])*(n-1-a.second + 1 + i);
  30. 					}
  31. 					p[i]=temp;
  32. 					q.push(a);
  33. 				}
  34. 				else {
  35. 					if(s)
  36. 					{
  37. 						cost+=(a.first*(i-a.second));
  38. 					}
  39. 					else {
  40. 						cost+=(a.first)*(n-1-a.second + 1 + i);
  41. 					}
  42.  
  43. 					p[i]=p[i]+a.first;
  44. 				}
  45. 			}
  46. 		}
  47. 		if(s && i==n-1 && !q.empty()) {
  48. 			i=-1;
  49. 			s=false;
  50. 		}
  51. 	}
  52. 	return cost;
  53. }
  54. int main()
  55. {
  56. 	int n;
  57. 	cin>>n;
  58. 	vector<int>r,p(n);
  59. 	for(int i=0; i<n; i++) {
  60. 		cin>>p[i];
  61. 	}
  62. 	r=p;
  63. 	reverse(r.begin(),r.end());
  64. 	cout<<min(fun(n,p),fun(n,r))<<endl;
  65. 	return 0;
  66. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Lupn1J
language:
C++ (gcc 8.3)
created:
8 hours 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!