Tävlingsprogrammering/Uppgifter/Röstköp

Röstköp (PO-onlinekvalet 2008)

Karl-Gunnar kandiderar till ordförandeposten i sin idrottsförening och vill inte riskera att förlora omröstningen. Han har lyckats få reda på vilken kandidat varje medlem tänker rösta på och tänker helt enkelt muta ett antal medlemmar så att de röstar på honom istället. Skriv ett program som beräknar hur många röster som måste köpas (d.v.s. medlemmar som behöver mutas) för att Karl-Gunnar ska vinna omröstningen. För att vinna krävs att man får fler röster än var och en av de andra kandidaterna.

Indata

På första raden står ett heltal: antalet kandidater (1 ≤ n ≤ 20). På andra raden står n heltal (mellan 0 och 1000): antalet röster varje kandidat skulle få utan mutor. Det första talet anger Karl-Gunnars röster.

Utdata

Programmet ska skriva ut en rad med ett heltal: det minsta antalet röster som behöver köpas för att Karl-Gunnar ska få fler röster än var och en av de övriga kandidaterna.

Exempel: Indata

4
2 5 7 8

Exempel: Utdata

5

Exempel: Förklaring

Karl-Gunnar kan t.ex. köpa 3 röster som skulle tillfallit den fjärde kandidaten samt 2 röster som skulle tillfallit den tredje kandidaten. Då får han själv 7 röster medan övriga kandidater får 5 röster.

Lösning

Att få fler röster än var och en av de andra kandidaterna innebär att få fler röster än den av de andra som har flest. Därför köper vi hela tiden röster från den som har flest röster, till dess att ingen har det längre. Ingen effektiv lösning behövs, vi kan ta en röst i taget (det blir ju maximalt 1001 mutor).

Lösningsexempel i C

#include <stdio.h>

int main() {
  int i, N, n[100], max, sum;
  scanf("%d", &N);
  for(i=0;i<N;i++) scanf("%d", &n[i]);
  max=0; 
  for(i=1;i<N;i++) max>?=n[i];   //Hitta det maximala antalet röster bland övriga kandidater
  sum=0;
  while(1) {
    for(i=1;i<N && max>=n[0];i++) if(n[i]==max) { //Köp röster av alla som har max så länge KG har färre
      n[i]--;
      n[0]++;
      sum++;
    }
    if(max<n[0]) break;  //Är vi färdiga?
    max--;   //Vid nästa genomgång har max-värdet minskat med 1
  }
  printf("%d\n",sum);
  return 0;
}