Dificultad: Fácil
Problema:
Dada una cadena $E$, ($|E| ≤ 500$) compuesta por los símbolos
Para mejor claridad veamos el caso de prueba:
#, + y - (La cadena no contendrá más de 7 # juntos) y una cadena de dígitos S, ($|S| =$ número de '#' en $E$). Acomodar cada uno de lo dígitos en $S$ en cada posición # en $E$ para que la operación que representa nos de como resultado el valor máximo.Para mejor claridad veamos el caso de prueba:
##+## 1234La mejor forma de acomodarlos para obtener el máximo es $32+41$ lo que nos da $73$ como resultado.
Solución:
Para encontrar el valor máximo de una suma tenemos que maximizar el valor de sus operandos mientras que para las restas tenemos que minimizarlo. Una forma de hacerlo es separar la cadena $E$ en grupos de #, de tal manera que llevemos la cuenta de qué tan grande es el número (cantidad de dígitos) y podamos identificar entre los que son positivos o negativos. Sabiendo esto repartiremos los números en $E$ haciendo que los de mayor valor queden en los grupos positivos con mayor cantidad de dígitos y los de menor valor queden en los negativos con mayor cantidad de dígitos.
Los dígitos se deben repartir en un orden peculiar para que el resultado nos de la solución deseada, y es que primero se deben repartir la cantidad más grande (en el caso del ejemplo anterior son las decenas, números 4 y 3) y luego las unidades. Una vez que se hizo esto se deben repartir a los grupos negativos los dígitos con menor valor siguiendo lo anteriormente dicho.
Después bastara con sumar/restar los valores resultantes de la operación anterior para obtener el resultado.
Los dígitos se deben repartir en un orden peculiar para que el resultado nos de la solución deseada, y es que primero se deben repartir la cantidad más grande (en el caso del ejemplo anterior son las decenas, números 4 y 3) y luego las unidades. Una vez que se hizo esto se deben repartir a los grupos negativos los dígitos con menor valor siguiendo lo anteriormente dicho.
Después bastara con sumar/restar los valores resultantes de la operación anterior para obtener el resultado.
Complejidad: $O(N log N)$ debido a la ordenación de los dígitos en $E$.
Código (C++):Para facilitarnos las cosas, definiremos una estructura que contenga la información que necesitamos acerca de los grupos de #.
struct Group{
int o; // Original index
int v; // Value of the group
int d; // Digit amount
int s; // Positive or negative: 1 or -1
int value(){ // Return the final value
return s * v;
}
};
Definimos además un arreglo
nums de tamaño k donde se almacenarán los dígitos de la cadena $E$ ordenados de manera descendente, un arreglo G de tamaño p de la estructura Grupo donde almacenaremos nuestros grupos ordenado del número positivo con mayor cantidad de dígitos al número negativo con menor cantidad de dígitos.
En el siguiente fragmento de código se reparten los dígitos a los grupos positivos:
int n = -1;
int neg;
int ii = 0;
int ix = 0;
n = G[0].d;
while(n > 0 && G[0].s > 0){
for(ix = 0; G[ix].d == n && ix <= p; ix++){
if(G[ix].s < 0) { break; }
G[ix].d--;
G[ix].v = (nums[ii] * pow(10,n-1)) + G[ix].v;
ii++;
}
n = G[0].d;
}
En este se reparten a ls números negativos, no sin antes invertir el orden de los números, dejando el arreglo nums ordenado de manera ascendente: reverse(nums+ii, nums+k);
neg = ix;
n = G[ix].d;
while(n){
for(; G[ix].d == n && ix <= p; ix++){
G[ix].d--;
G[ix].v = (nums[ii] * pow(10,n-1)) + G[ix].v;
ii++;
}
n = G[neg].d;
}
Para finalizar, basta con sumar los valores de nuestro todas nuestras estructuras
Grupo para obtener el resultado: int res = 0;
for(i = 0; i <= p; i++){
res += G[i].value();
}
printf("%d\n", res);
