Tävlingsprogrammering/Uppgifter/Storstad
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.
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
redigeraFö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;
}