fork(1) download
  1. // (X[i],Y[i]) legyen a tűzcsapok koordinátái, ekkor, ha (x,y) a tűzoltóság tervezett helye
  2. // akkor a kiérkezés várható ideje c(x,y), ahol
  3. // c(x,y)=sum(i=0,K-1,p[i]*abs(X[i]-x))+sum(i=0,K-1,p[i]*abs(Y[i]-y))=s(x)+s(y)
  4. // Így az optimum min(s(x))+min(s(y)), továbbá két tűzcsapvetület között
  5. // a célfüggvény lineárisan változik, ebből egyrészt az is következik,
  6. // hogy az optimumot tűzcsapvetületek között is találunk,
  7. // azaz lesz i és j, hogy az optimum (X[i],Y[j]) helyen is felvétetik.
  8.  
  9. #include <cstdio>
  10. #include <queue>
  11.  
  12. using namespace std;
  13. typedef long long int lli;
  14.  
  15. #define maxn 100000
  16. int main(void){
  17.  
  18. priority_queue<lli>px;
  19.  
  20. int h,i,N,M,K,ox[2],p[maxn],px1,P=0;
  21. lli a[maxn][2],x,x1,x2,f,s,opt;
  22.  
  23. scanf("%d%d%d",&N,&M,&K);
  24. for(i=0;i<K;i++){scanf("%lld%lld%d",&a[i][0],&a[i][1],&p[i]);P+=p[i];}// P az összes p összege
  25.  
  26. for(h=0;h<2;h++){// h=0-ra az x irányú vetületekkel foglalkozunk
  27. // h=1-re az y irányúakkal (de ekkor is x1,px1 stb. a jelölés)
  28. s=0;
  29. for(i=0;i<K;i++){
  30. px.push(-(a[i][h]<<7)-p[i]);// alsó 7 biten tárolom p értékét, ez jó lesz, mert 1<=p<=100<128 igaz.
  31. s+=(lli)p[i]*a[i][h];
  32. }
  33.  
  34. x1=0;px1=0;// Vigyázat! x1=0 biztosan nem utca/sugárút sorszáma
  35. // px1 az összes p összege x1=0-ig, ez triviálisan nulla
  36. for(i=0;i<K;i++){
  37. f=-(px.top());px.pop();// mindig a legkisebb x koordinátájú pontot kapom meg,
  38. // mert u<v-re és tetszőleges 0<=p1,p2<128-ra: 128*u+p1<128*v+p2
  39. // Ha az utca u-ról v-re változik és közte nincsen tűzcsap(vetület), akkor
  40. // az új költség c+(v-u)*(2*P-S), ahol c a régi költség
  41. // P pedig u-ig a p-k összege, míg S az összes p összege.
  42. x2=f>>7;// vetület kinyerése
  43. s+=(lli)(x2-x1)*(2*px1-P);px1+=f&127;x1=x2;// új költség/p összeg/vetület
  44. if(i==0||s<opt){opt=s;ox[h]=x1;}// új optimumot találtunk
  45. }
  46. }
  47. printf("%d %d\n",ox[0],ox[1]);
  48. return 0;
  49. }
  50.  
Success #stdin #stdout 0s 5304KB
stdin
4 3 3
1 1 10
3 2 20
1 2 70
stdout
1 2