fork(1) download
copy 
  1. // O(n*log(n)) megoldás
  2. // Egy csoki áthelyezése felbontható olyan áthelyezésekre, amikor egy gyerek, az i-edik
  3. // az (i+1)-ediknek ad egy csokit, vagy kap tőle egyet.
  4. // i-edik gyerek d(i) darabot adjon az (i+1)-ediknek (0<=i<n és az n-edik ugyanaz, mint a 0-dik)
  5. // ((ha d(i)<0, akkor ő valójában kapni fog az (i+1)-ediktől))
  6.  
  7. // Ha delta=d(n-1), akkor mindegyik d() számolható:
  8. // legyen s(i)=sum(k=0,i,a(k)); t(i)=sum(k=0,i,b(k)), ekkor
  9. // az első i+1-nek kell összesen s(i) csoki, kezdetben van nekik t(i) és összesen ez -d(i)+delta-val nő
  10. // azaz s(i)=t(i)-d(i)+delta, ebből: d(i)=t(i)-s(i)+delta
  11. // így az átrendezés ideje: 
  12. // S=sum(i=0,n-1,abs(d(i)))=sum(i=0,n-1,abs(t(i)-s(i)+delta))=sum(i=0,n-1,abs(delta-c(i))), ahol
  13. // c(i)=s(i)-t(i)
  14. // az S alakjából látható, hogy az optimum (valamely i-re) delta=c(i) pontban is felvétetik.
  15. // (két szomszédos c(i) között a fv. lineáris és +-végtelenben végtelen)
  16.  
  17. // az még nem látható, hogy tetszőleges deltára az áthelyezések tényleg megvalósíthatóak,
  18. // de ez könnyű: ha a(i)<b(i) valamely i-re (akkor tetszőleges deltára) igaz, hogy ő adni fog egy
  19. // szomszédjának (különben még több csokija lenne), adjon egy csokit a szomszédjának ezzel az optimum
  20. // eggyel csökken és indukció. (ha a(i)>=b(i) minden i-re, akkor itt mindenhol = van és az optimum nulla).
  21.  
  22. #include <algorithm>
  23. #include <cstdio>
  24.  
  25. using namespace std;  
  26.  
  27. #define maxn 100005
  28.  
  29. typedef long long int lli;
  30. int main(void){
  31.  
  32.   int i,n,a,b,total=0,c[maxn];
  33.   lli ans,s,u;
  34.  
  35.   scanf("%d",&n);
  36.   for(i=0;i<n;i++){
  37.       scanf("%d%d",&a,&b);
  38.       total+=a-b;
  39.       c[i]=total;
  40.   }
  41.   sort(c,c+n);
  42.  
  43.   u=0;
  44.   for(i=0;i<n;i++)u+=c[i];
  45.   for(i=0;i<n;i++){
  46.       // delta=c[i] kipróbálása
  47.       s=u+(lli)(-n+2*i)*c[i];
  48.       if(i==0||s<ans)ans=s;
  49.       u-=2*c[i];
  50.   }
  51.   printf("%lld\n",ans);
  52.  
  53.   return 0;
  54. }
  55.  
Success #stdin #stdout 0s 3616KB
comments (?)
stdin
copy 
4
7 1
3 4
9 2
1 13
stdout
copy 
13
https://ideone.com/vJP729
language:
C++ (gcc 8.3)
created:
9 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!