SlimeXSlimeRancher2
SRM 506 · 2010-11-01 · by dolphinigle
SRM 506 · 2010-11-01 · by dolphinigle · Brute Force, Greedy
Problem Statement
Problem Statement
You are playing a game titled Slime Rancher 2. You will be training slimes in this game.
You have a slime-in-training. Associated with the slime are N attributes, numbered 0 through N-1, each represented by a positive integer. You are givenint[] attributes containing N integers : the i-th integer is the initial value of the i-th attribute for the slime. After the training is complete, each of the slime's attributes will either stay the same or increase to some positive integer less than or equal to 999. None of the attributes will decrease in value. The weight of the training is defined as the sum of the differences between the final and initial values of all the attributes for the slime.
You are a master slime breeder, and you're able to obtain any possible final values for a slime's attributes. This time, you would like to create a well-balanced slime. A slime is well-balanced if all of its attributes have equal values. What is the minimum possible weight of the training?
You have a slime-in-training. Associated with the slime are N attributes, numbered 0 through N-1, each represented by a positive integer. You are given
You are a master slime breeder, and you're able to obtain any possible final values for a slime's attributes. This time, you would like to create a well-balanced slime. A slime is well-balanced if all of its attributes have equal values. What is the minimum possible weight of the training?
Constraints
- attributes will contain between 2 and 50 elements, inclusive.
- Each element of attributes will be between 1 and 999, inclusive.
Examples
0)
{1,2,3}
Returns: 3
Train the slime such that all of its attributes are equal to 3. The total weight of the training is |3 - 1| + |3 - 2| + |3 - 3| = 3.
1)
{5,5}
Returns: 0
This slime is already well-balanced.
2)
{900,500,100}
Returns: 1200
3)
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,999}
Returns: 48902
4)
{1,1,1,1,1}
Returns: 0
Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SlimeXSlimeRancher2 with a public method int train(vector<int> attributes) · 103 test cases · 2 s / 256 MB per case