Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Solucao Informatica Avancado Semana 59
- // Thiago Mota
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 100010;
- int f[maxn];
- int n;
- int main() {
- int k;
- cin >> n >> k;
- int l=maxn, r=-1; // l = menor valor, r = maior valor
- for(int i=1;i<=n;i++) {
- int x;
- cin >> x;
- l = min(l, x);
- r = max(r, x);
- f[x]++;
- }
- int ans=0;
- // Two pointers
- while(true) {
- while(l < r && f[l] == 0) l++; // Se a frequencia de l for igual a 0 significa que o menor valor esta mais a direita.
- while(l < r && f[r] == 0) r--; // Mesma coisa aplicada ao r.
- if(r - l <= k) break;
- if(l >= r) break;
- // Agora l e r mantem respectivamente o menor e o maior valor.
- int c = min(f[l], f[r]);
- // Para aumentar l em 1, basta aumentar a frequencia de l+1 e diminuir de l
- f[l+1] += c;
- f[l] -= c;
- // Para diminuir r em 1, basta diminuir a frequencia de r e aumentar de r-1
- f[r] -= c;
- f[r-1] += c;
- ans += c; // Aumenta o número de operacoes em c, pois fizemos isso para "c" ocorrencias de l e r
- }
- cout << ans << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement