fork download
copy 
  1. #include <iostream>
  2. #include <fstream> 
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. using namespace std;
  7.  
  8. int n;
  9.  
  10. long long calcVal(int *dat, long long test)
  11. {
  12.     //     cout << "Calcval - calcolo spesa per livello: " << test << endl;
  13.     long long count=0;
  14.     for (int i=0; i<n; i++) {
  15.         count+=abs(test-dat[i]);
  16.     }    
  17.     return count;
  18. }
  19.  
  20. int compare (const void * a, const void * b)
  21. {
  22.     return ( *(int*)a - *(int*)b );
  23. }
  24.  
  25. long long findBMinCost(int Min, int Max, int *data) {
  26.     long long cost, costDTest, costSTest; 
  27.     int dTest, i=Min, j=Max, m;
  28.     dTest=1;
  29.     do { 
  30.         m=(i+j)/2;  //m=metà intervallo
  31.         // provo valori centrale, sinistro e destro
  32.         costSTest=calcVal(data, m-dTest);
  33.         cost=calcVal(data, m);
  34.         costDTest=calcVal(data, m+dTest);
  35.         //         cout << "Livello " << m-dTest << " costo "<< costSTest << endl;
  36.         //         cout << "Livello " << m << " costo "<< cost << endl;
  37.         //         cout << "Livello " << m+dTest << " costo "<< costDTest << endl;
  38.         if (costSTest<cost)
  39.             j=m-1;
  40.         else if (costDTest<cost)
  41.             i=m+1;            
  42.     } while(costSTest<cost || costDTest<cost);
  43.     return cost;
  44. }
  45.  
  46.  
  47. int main(void) {
  48.     unsigned long long count, partial=0, media;
  49.     long double rMedia=0;
  50.     int Min=1000000000, Max=0;
  51.     ifstream in("input.txt");
  52.     ofstream out("output.txt");
  53.     in>>n;
  54.     int dati[n];
  55.     for (int i=0; i<n; i++) {
  56.         in >> dati[i];
  57.         dati[i]-=i;     // sottraggo il livello da raggiungere, la spesa si calcola ora per livellare in orizzontale
  58.         if (Min>dati[i])
  59.             Min=dati[i];
  60.         if (Max < dati[i])
  61.             Max=dati[i];
  62.     }
  63.     in.close(); 
  64.  
  65.  
  66.     qsort(dati, n, sizeof(int), compare);
  67.  
  68. //     for (int i=0; i<n; i++)
  69. //         cout << dati[i] << " ";
  70. //     cout << endl; 
  71.  
  72.     count= findBMinCost(Min, Max, dati);
  73.  
  74. //    cout  << count;
  75.     out << count;
  76.     out.close();
  77.  
  78.     return 0;
  79. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5
5 2 4 6 4
stdout
copy 
Standard output is empty
https://ideone.com/2YXwWZ
language:
C++ (gcc 8.3)
created:
19 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!