Solução Colônia de Formigas - Semana 2

Solução por Lucca Siaudzionis

Vamos dificultar um pouquinho a questão: não necessariamente há um elemento majoritário, neste caso, diga que não há. Resolver este problema é um processo de duas etapas:

  1. Achar um elemento que seja candidato a ser a resposta.
  2. Checar caso o elemento encontrado acima é majoritário.

1) Achar um candidato

O algoritmo para esta etapa roda em O(n) e é conhecido por Algoritmo de Moore. A ideia básica do algoritmo é cancelar cada ocorrência de um elemento e com todos os elementos diferentes de e e ir deixando esse número de ocorrências num contador c (subtraindo um quando é diferente de e). Caso o c chegue a zero, atualizamos o valor de e. O nosso último valor de e é nosso candidato. Inicializamos e para o primeiro elemento do array e c para 1.

2) Checar se é majoritário

Ao final, simplesmente percorremos o array e contamos o número de ocorrências do nosso candidato e checamos se é majoritário.

Abaixo, o código para o problema original:


//
// majority.cpp
// programas2
//
// Created by Lucca Siaudzionis on 27/03/13.
// Copyright (c) 2013 Luccasiau. All rights reserved.
//
#include <cstdio>
#define MAXN 3000005
int myv[MAXN];
int main(){
int n;
scanf("%d",&n);
for(int i = 1;i<=n;i++) scanf("%d",&myv[i]);
int index = 1;
int count = 1;
for(int i = 2;i<=n;i++){
if(myv[i] == myv[index]) count++;
else count--;
if(!count){
index = i;
count = 1;
}
}
printf("%d\n",myv[index]);
return 0;
}