HackerRank: Equal

HackerRank: Equal
Christy is interning at HackerRank. One day she has to distribute some chocolates to her colleagues. She is biased towards her friends and may have distributed the chocolates unequally. One of the program managers gets to know this and orders Christy to make sure everyone gets equal number of chocolates.

But to make things difficult for the intern, she is ordered to equalize the number of chocolates for every colleague in the following manner,

For every operation, she can choose one of her colleagues and can do one of the three things.
(i) She can give one chocolate to every colleague other than chosen one.
(ii) She can give two chocolates to every colleague other than chosen one.
(iii) She can give five chocolates to every colleague other than chosen one.

Calculate minimum number of such operations needed to ensure that every colleague has the same number of chocolates.

Christy has to equalize the number of chocolates for all the coworkers. The only action she can make at every operation is to increase the count of every others' chocolate by 1,2 or 5 except one of them. This is equivalent to saying, christy can take away the chocolates of one coworker by 1, 2 or 5 while keeping others' chocolate untouched.

Let's consider decreasing a coworker's chocolate as an operation. To minimize the number of operations, we should try to make the number of chocolates of every coworker equal to the minimum one in the group(min). We have to decrease the number of chocolates the ith person A[i] by (A[i] - min). Let this value be x. For this you may consider Coin change algorithms.

we now follow a greedy algorithm so number of operations required is minimum. This can be done in k operations.

k = x/5 +(x%5)/2 + (x%5)%2 

Let f(min) be sum of operations performed over all coworkers to reduce each of their chocolates to min.

However, sometimes f(min) might not always give the correct answer. It can also be a case when

f(min) > f(min-1)

but it is safe to assume that

f(min) < f(min-5)

as f(min-5) takes N operations more than f(min) where N is the number of coworkers.

Therefore, if

A = {min,min-1,min-2,min-3,min-4} 

then,

f(A) <= f(min) < f(min-5)

Compute f(y) ∀ y ∈ A and print the minimum as the answer.

long long int functn (long long int temp)  // similar to greedy Coin-change
{
    long long int x=0;
    if(temp>=5)
    {
        x = temp/5;
        temp = temp%5;
    }
    if(temp>=2)
    {
        x += temp/2;
        temp = temp%2;
    }
    x += temp;
    return x;

}

int array_smallest(long long int array[],int array_length)
{
    long long int smallest = INT_MAX;
    long long int i;
    for (i = 0; i < array_length; i++)
    {
        if (array[i] < smallest) {
            smallest = array[i];
        }
    }
    return smallest;
}

long long int mod(long long int x)
{
    if(x>0)
        return x;
    else
        return (-1)*x;
}

int main()
{
    long long int T,N,i,j,min,sum,temp;
    cin>>T;
    while(T--)
    {
        min = 1000000;
        cin>>N;
        int A[N];
        for(i=0 ; i< N ; i++)
        {
            cin>>A[i];
            if(A[i]<min)
                min = A[i];
        }
        long long int sum[6];
        for(j=0 ; j<=5 ; j++)
        {
            sum[j]=0;
            for(i=0 ; i< N ; i++)
            {
                temp = mod(A[i] - (min-j));
                sum[j] = sum[j] + functn(temp);
            }
        }
        cout<<array_smallest(sum,6)<<endl;
    }
    return 0;
}

https://www.nowtoshare.com/zh/Article/Index/70569
public static int minToEqual(int[] chocolates){ int [] options = new int[]{1,2,5}; int step =Integer.MAX_VALUE; int min=Integer.MAX_VALUE; for(int i=0; i<chocolates.length;i++){ min =Math.min(min, chocolates[i]); } HashMap<Integer, Integer> memo = new HashMap<>(); for(int realMin=Math.max(0,min-4); realMin<=min;realMin++){ int step_cur =0; for(int i=0; i<chocolates.length;i++){ step_cur+=minStep(chocolates[i]-realMin,options, memo); } step =Math.min(step_cur,step); } return step; } public static int minStep(int offset, int[] options, HashMap<Integer, Integer> memo){ if(offset==0) return 0; if(memo.containsKey(offset)) return memo.get(offset); int step =Integer.MAX_VALUE; for(int option : options){ if(offset >=option) step = Math.min(step, minStep(offset-option,options,memo)+1); } memo.put(offset, step); return step; } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner scan = new Scanner(System.in); int cases = scan.nextInt(); for(int i=0;i<cases; i++){ int colleaguesNum = scan.nextInt(); int[] chocolates = new int[colleaguesNum]; for(int k=0;k<colleaguesNum;k++){ chocolates[k] = scan.nextInt(); } System.out.println(minToEqual(chocolates)); } }

http://blog.csdn.net/junchen1992/article/details/52228803

逆向思维：(1)题目问的是让我们“加”巧克力使得每个人最终巧克力数量一样。这等价于“减”巧克力使得每个人最终巧克力数量一样。(2)用“减”的方法，最终的目标是使得每个人的巧克力数量为原输入数组的最小值或者任意小于该值但不为负。

http://winoros.logdown.com/posts/245627-hackerrank-equal

除某个数之外都增加，可以等效成只有一个数减少。
那么直观来看，最少的应该是所有的数都减到最小的数，记这个和为f(min)
但是因为每次可以-1，可以-2，可以-5。所以这时并不一定是都减到最小的数合适。
比如1 5 10，如果减到1，需要9/5+4/2=3 4/2=2 3+2=5 而如果都减到0，就是5/5=1 10/5=2 1+2+1=4
所以，不能简单的算f(min)。但是注意到f(min-5)是肯定小于f(min)的在往小了肯定是大于f(min)的，所以我们至多只要算导f(min-5)
那么就是o(n)辣

        for(int i = 0; i < n; ++i) {
            scanf("%d", a+i);
            minn = min(minn, a[i]);
        }
        int ans = 100000000;
        for(int i = -5; i <= 0; ++i) {
            int this_ans = 0;
            for(int j = 0, delta; j < n; ++j) {
                delta = a[j] - i - minn;
                this_ans += delta/5 + delta%5/2 + delta%5%2;
            }
            ans = min(this_ans, ans);
        }
        printf("%d\n", ans);
    }

int minVal = A[0];

for(int i = 1; i < N; ++i){

    if (A[i] < minVal){

        minVal = A[i];

    }

}

int minCount = Integer.MAX_VALUE;

for(int i = 0; i <= 5; ++i){

    int count = 0;

    for(short j = 0; j < N; ++j){

        short V = (short)(A[j] - (minVal - i));

        count += V/5 + (V %= 5)/2 + (V & 1);

    }

    if (count < minCount){

        minCount = count;

    }

}