i was create a algorithm to solved 671B and i did that:
that running with O( n*log(n) ) { well, i think so } but th judgement gave "RunTime_ERROR", why do you think??? and how can i better my algorithm??
#include <iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
/*
1) idead: using two priority queue to recover the Max and Min values and subtraccion each other.
time => O( n*log(n)*k )--> can swap values max and min on Minimo and Maximo,
2) idead : using a map tree to sort all values and operate on tree
time => O( n*log( n ) + K*log( n ) ) --> find max/min in O( log(n) )
3) using range of values are diference between min again this value, and operate using range to reduce
K on the time.
time => O( n*log^2( n ) )
*/
unsigned int Rango = 1;
unsigned int x = 0;
unsigned int K = 0;
unsigned int N = 0;
unsigned int Mover = 0;
unsigned int Mayor, Menor;
unsigned int LimiteMx, LimiteMn;
unsigned int Civiles[ 500000 ];
unsigned int BuscarSgte(){
int fin = N -1 ; int inicio = 0;
int medio = (N - 1)/2;
while( fin != inicio + 1 ){
if( Civiles[ medio ] > Civiles[ 0 ] ) fin = medio;
else if( Civiles[ medio ] == Civiles[ 0 ] && Civiles[ medio + 1] == Civiles[ 0 ] ) inicio = medio;
else break;
medio = ( fin + inicio )/2;
}
return ( Civiles[ medio + 1 ] == Civiles[0] )? medio + 1 : medio ;
}
unsigned int BuscarAnterior(){
int medio = (N-1)/2;
int fin = N - 1; int inicio = 0;
while( fin != 1 + inicio ){
if( Civiles[ medio ] < Civiles[ N - 1 ])
inicio = medio;
else if( Civiles[ medio ] == Civiles[ N - 1 ] && Civiles[ medio - 1 ] == Civiles[ N - 1 ] )
fin = medio;
else
break;
medio = ( fin + inicio ) / 2;
}
return ( Civiles[ medio ] == Civiles[ N - 1] )? medio: medio + 1;
}
void Actualizar( int Mn, int Mx , int Base ){
for( int i = 0; i < Base ; i++ ){
Civiles[ Mn - i ] += 1;
Civiles[ Mx + i ] -= 1;
}
}
int main()
{
scanf("%i %i", &N , &K );
for( int i = 0; i < N; i++ ){
scanf("%i", &Civiles[i] );
}
sort(Civiles, Civiles+N);
while( K > 0 ){
if( Civiles[ 0 ] + 1 == Civiles[ N - 1 ] || Civiles[0] == Civiles[ N - 1 ] ) break;
LimiteMx = BuscarAnterior();
LimiteMn = BuscarSgte();
Mayor = ( N - LimiteMx )*( Civiles[ N - 1 ] - Civiles[ LimiteMx - 1 ] );
Menor = ( LimiteMn + 1 )*( Civiles[ LimiteMn + 1 ] - Civiles[ 0 ] );
Mover = min( Menor, Mayor );
if( K <= Mover ){
Actualizar( LimiteMn , LimiteMx , K );
K = 0;
}else{
Actualizar( LimiteMn, LimiteMx , Mover );
K = K - Mover;
}
}
cout << Civiles[ N - 1 ] - Civiles[ 0 ] ;
return 0;
}