Tävlingsprogrammering/Uppgifter/Storstad

Från Wikibooks
Hoppa till navigering Hoppa till sök

Storstad

Deltagarna i den svenska programmeringsolympiaden älskar geometri, och det med rätta. Den största favoriten bland geometrierna är den så kallade manhattangeometrin. Manhattanavståndet mellan två punkter P och Q i ett regelbundet rutnät beskriver hur många punkter man måste passera för att ta sig från P till Q, givet att man bara får gå horisontellt och vertikalt.

Om P =(x1,y1) och Q =(x2,y2), så beräknas manhattanavståndet mellan punkterna som abs(x1−x2)+abs(y1−y2). abs(a) betecknar absolutbeloppet för talet a, dvs vi ignorerar minustecknet om talet är negativt.

Nu är det dags för dig att visa hur mycket du älskar geometri. Du ska planera din flytt till en storstad där manhattanavstånd gäller. Du har N stycken vänner som bor i storstaden, men du har bara M lägenheter att välja på. Din uppgift är att lista ut hur du ska välja lägenhet så att summan av manhattanavstånden till alla dina N vänner från din lägenhet är så liten som möjligt.

Delpoäng

På det här problemet kan du samla poäng trots att du inte löser problemet helt och hållet.

  • För 40% av poängen gäller att 1≤N≤104 och 1≤M≤100.
  • För full poäng måste din lösning hantera 1≤N≤105 och 1≤M≤105.
De svarta prickarna representerar lägenheter vi kan välja på i storstaden, och de grå prickarna markerar var våra vänner bor. Om vi väljer lägenheten i (0,0) så blir summan av avstånden till vännerna 4+6+6+9=25. Väljer vi lägenheten i (1,6) så blir summan av avstånden 3+5+6+9=23. Väljer vi den sista lägenheten så blir summan av avstånden 1+4+6+4=15, och att välja lägenheten i (5,5) är då optimalt.

Indata

På första raden i indata finns två heltal N och M, separerade av ett mellanslag. Sedan följer N rader med två par av heltal −10000≤xi≤10000 och −10000≤yi≤10000, separerade av mellanslag. Dessa beskriver på vilka korsningar i staden som dina vänner bor. Slutligen följer M rader med par av tal −10000≤xi≤10000 och −10000≤yi≤10000, separerade av mellanslag, som beskriver på vilka korsningar i staden du kan välja att bo. Notera att det kan finnas flervåningshus i storstaden (en punkt kan förekomma flera gånger i indata).

Utdata

Ditt program ska skriva ut ett enda tal på en rad: den minsta möjliga summan av manhattanavstånden till dina N vänner från din lägenhet.

Exempel 1

4 3
2 2
5 4
2 4
5 1
5 5
0 0 
1 6

ska ge svaret

15

Exempel 2

2 2
0 0
0 2
2 0
2 2

ska ge svaret

6

Exempel 3

1 1
1 1
1 1

ska ge svaret

0

Lösning[redigera]

För att erhålla delpoängen räcker det att för varje lägenhet summera avståndet till vännerna med en enkel loop och välja den lägenhet som ger lägst summa. Denna lösning har tidskomplexiteten O(N*M).

För stora indata tar denna naiva lösning för lång tid. Tricket är att undvika den kostsamma dubbel-loopen och istället låta varje vän bidra till avståndssumman för många lägenheter samtidigt, genom en så kallad svep-algoritm som sveper igenom punkterna ett konstant antal gånger för att samla information.

För att åstadkomma detta delar vi först upp problemet i två identiska delproblem, ett som beräknar summan av avstånden i x-led och ett som beräknar summan av avstånden i y-led. Tack vare manhattan-geometrin ges ju den sökta totalavståndet av summan av dessa tal. Vidare delar vi upp varje sådant endimensionellt delproblem i två delar, en som för varje kandidatlägenhet på position xk endast tar hänsyn till de vänner som bor på xj < xk, och en som bara tar hänsyn till de vänner som bor på xj > xk (eller ekvivalent för y-koordinaten). Uppenbarligen ges nu totalavståndet av summan av dessa fyra enklare delproblem.

För varje delproblem går vi nu igenom alla punkterna, både kandidatlägenheter och vännernas positioner, i stigande (eller sjunkande) ordning med avseende på den aktuella koordinaten (x eller y). När vi stöter på en vän ökar vi en räknare nact som anger hur många av vännerna som vi har passerat och som därmed bidrar till att öka avståndssumman. När vi vandrar ett avstånd dx fram till nästa punkt ökar vi på den uppsamlade avståndssumman genom att multiplicera dx med nact. Slutligen, när vi kommer till en kandidatlägenhet sätter vi den uppsamlade avståndssumman som svar på delproblemet för denna kandidatlägenhet.

Svepningen över punkterna går på linjär tid och det tidsbegränsande steget blir nu sorteringen av punkterna, och vi får därför tidskomplexiteten O([N+M] log [N+M]).

Det gäller också att se till att genomgående använda 64-bitars heltal för att undvika overflow.

Lösning i C:

#include <stdio.h>
#include <stdlib.h>

typedef long long ll;

void scan(ll n, ll np, ll x[],ll ord[], ll d[], ll rev) {  //rev=1 för stigande ordning, -1 för sjunkande ordning   
  ll i,j,dx;
  ll nact=0,last=0,sum=0;    //Värdet på last spelar ingen roll eftersom nact=0
  for(i=0;i<n;i++) {
    j=(rev==-1)?ord[n-1-i]:ord[i];     //Index för nästa punkt i ordningen, framåt eller bakåt
    dx=(x[j]-last)*rev;  //Avståndet vi har svept över räknat från föregående punkt, multiplicerat med rev för att alltid vara positivt
    sum+=nact*dx;          //Öka avståndssumman med detta avstånd multiplicerat med antalet aktiva vänner
    if(j>=np) d[j]+=sum;     //Om det är en lägenhet, addera svaret på delproblemet (sum) till det totala svaret
    else nact++;            //Annars är det en vän, så öka antalet "aktiva" vänner
    last=x[j];               //Spara koordinaten inför nästa dx-beräkning
  }
}
 
ll x[200000],y[200000];
 
int fcmpx(const void *v1, const void *v2) {   //Jämförelsefunktioner för qsort
  return x[*(ll*)v1]-x[*(ll*)v2];
}
int fcmpy(const void *v1, const void *v2) {
  return y[*(ll*)v1]-y[*(ll*)v2];
}
 

int main() {
  ll d[200000],ordx[200000], ordy[200000],i,n,np,min;
  scanf("%lld %lld", &np, &i);
  n=np+i;       //Totalt antal punkter, vi behandlar vänner och lägenheter lika
  for(i=0;i<n;i++) {
    scanf("%lld %lld", &x[i],&y[i]);
    if(i>=np) d[i]=0;      // index >=np innebär att det är en lägenhet 
    ordx[i]=ordy[i]=i;          //Skapa två uppsättningar index att sortera
  }
  qsort(ordx,n,sizeof(ll),fcmpx);    //Sortera indexen efter x-koordinat
  qsort(ordy,n,sizeof(ll),fcmpy);    //Sortera indexen efter y-koordinat
  scan(n,np,x,ordx,d,1);      //Svep x framlänges
  scan(n,np,x,ordx,d,-1);     //Svep x baklänges
  scan(n,np,y,ordy,d,1);      //Svep y framlänges
  scan(n,np,y,ordy,d,-1);     //Svep y baklänges
  min=1LL<<62;   
  for(i=np;i<n;i++)  {      //Loopa igenom lägenheterna och välj minsta summan
     if(d[i]<min)  min=d[i];
  }
  printf("%lld\n", min);
  return 0;
}