kburnik

C++ - Zadatak Vrsar

Jan 9th, 2013
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. Pripreme 2013 - C++ radionica
  4.  
  5. Zadatak: Vrsar
  6.  
  7. Autor zadatka: HSIN
  8.  
  9. Ponudjeno rjesenje: Kristijan Burnik, udruga informaticara Bozo Tezak
  10.  
  11. Datum rjesavanja: 2013-01-09
  12.  
  13. */
  14. #include <iostream>
  15. #include <cstdlib>
  16. #include <vector>
  17.  
  18.  
  19.  
  20. using namespace std;
  21.  
  22. // cijene za "gore" i "dolje"
  23. int a,b;
  24.  
  25. // visine su u ovom vektoru
  26. vector <int> h;
  27.  
  28. // funkcija koja vraca ukupan trosak ravnanja na neku zadanu razinu
  29. int costOfLevel(int level) {
  30.     int hs = h.size();
  31.     int cost = 0;
  32.     for (int i = 0 ; i < hs; i++){
  33.  
  34.         if (h[i] < level) {
  35.             // nivo je  manji od zeljenog
  36.             cost += (level - h[i]) * a;
  37.         } else if (h[i] > level) {
  38.             // nivo je veci od zeljenog
  39.             cost += (h[i] - level) * b;
  40.            
  41.         }
  42.     }
  43.     return cost;
  44.    
  45. }
  46.  
  47. int main() {
  48.  
  49.     int n,m;
  50.    
  51.     cin >> n >> m;
  52.        
  53.     // ukupan broj razina
  54.     int t = n * m;
  55.    
  56.     // visine su na globalnom vektoru h
  57.     h.resize(t);
  58.    
  59.     // unos visina
  60.     for (int i = 0; i < t;  i++)
  61.         cin >> h[i];
  62.    
  63.    
  64.     // cijene su globalne
  65.     cin >> a >> b;
  66.    
  67.     // sortiram kako bismo dobili minimum i maksimum razina,
  68.     // ispod ili iznad se ne isplati ici
  69.     sort(h.begin(),h.end());
  70.    
  71.     // neka veoma velika vrijednost, veca od najveceg moguceg troska
  72.     int minCost = 0x7FFFFFFF;
  73.    
  74.    
  75.     // trazimo minimalni trosak medju svim razinama od min razine do max razine
  76.     // s obzirom na velicine ulaznih podataka, ovo je sasvim u redu
  77.     // a slozenost je pritom kvadratna
  78.     for (int level = h[0] ; level <= h[t-1] ; level++ ) {
  79.         minCost = min(minCost, costOfLevel(level));
  80.     }
  81.    
  82.     // minimalni trosak ravnanja
  83.     cout << minCost << endl;
  84.    
  85.    
  86.    
  87.     system("pause");
  88.    
  89.     return 0;
  90. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×