Startup
Comentário escrito por João Pedro Castro
Podemos visualizar a hierarquia dessa empresa como um grafo, onde os vértices (funcionários) tem outros vértices se ligando à ele (os subordinados). Além da estrutura do grafo, para cada funcionário vamos guardar seu chefe, salário, e a quantidade de subordinados com os quais ele está insatisfeito. Também é necessário guardar a quantidade de funcionários insatisfeitos no total, chamaremos esse valor de $$f$$.
Após montar o grafo (feito com as arestas sendo: $$\text{chefe} \rightarrow \text{subordinado}$$), receber o chefe de cada um e o salário, para preencher a quantidade de insatisfações basta percorrer o grafo começando do vértice 1 e aumentando o valor de $$insatisfacoes[vertice]$$ em uma unidade toda vez que $$salario[subordinado] > salario[vertice]$$, quando isso acontecer, também aumente $$f$$ em 1 caso $$insatisfacoes[vertice] = 0$$, já que o estado do $$vertice$$ vai mudar de satisfeito para insatisfeito.
Para todo funcionário $$i$$ atualizado a ideia é checar se o “estado” (satisfeito ou insatisfeito) de seu chefe e dele mesmo (em relação ao seus subordinados) foram alterados, já que eles são os únicos com os quais isso pode ter acontecido. E isso pode ser feito com uma série de estruturas condicionais, que se resumem à:
- (chefe insatisfeito antes com o funcionário) e (chefe satisfeito agora)
- (chefe satisfeito antes com o funcionário) e (chefe insatisfeito agora)
Agora, para achar o valor de $$f$$ (a resposta) atualizado, é só seguir o seguinte algoritimo:
- Se $$i \neq 1 ~\&~ salario[i] \geq salario[chefe[i]] ~\&~ novoSalario > salario[chefe[i]]$$
- $$insatisfacoes[chefe[i]]++$$
- Se $$insatisfacoes[chefe[i]] = 1$$ (novo chefe insatisfeito):
- $$f++$$
- Se não se: $$salario[i] > salario[chefe[i]] ~\&~ salario[chefe[i]] \geq novoSalario$$
- $$insatisfacoes[chefe[i]]–$$
- Se $$insatisfacoes[chefe[i]] = 0$$ (chefe satisfeito de novo):
- $$f–$$
- Para cada subordinado $$u$$ de $$i$$:
- Se $$salario[i] \geq salario[u] ~\&~ salario[u] > novoSalario$$:
- $$insatisfacoes[i]++$$
- Se $$insatisfacoes[i] = 1$$ (novo chefe insatisfeito):
- $$f++$$
- Se não se: $$salario[u] > salario[i] ~\&~ novoSalario \geq salario[u]$$:
- $$insatisfacoes[i]–$$
- Se $$insatisfacoes[i] = 0$$ (chefe satisfeito de novo):
- $$f–$$
- Se $$salario[i] \geq salario[u] ~\&~ salario[u] > novoSalario$$:
- $$salario[i] = novoSalario$$
- $$imprimir~f$$
Assim você também garante que os valores de $$insatisfacoes$$ e $$f$$ sempre permanecem atualizados. Segue a solução em C++:
https://gist.github.com/ortsc/7a6c49b1e6b6a81059e94d3342190947