面试笔试算法题备考（一）--阿里巴巴--排序

sjbin 2021-09-08 原文

题目描述

等级：中等

知识点：排序、贪心

查看题目：数组变换

给出一个长度为 n 的数组，和一个正整数 d。

你每次可以选择其中任意一个元素 a[i] 将其变为 a[i] + d 或 a[i] – d，这算作一

次操作。

你需要将所有的元素全部变成相等元素，如果有解，请输出最小操作次数，如果

无解请输出 -1。

输入数字 n、数字 d，和一个长度为 n 的数组 a。1 <= n <= 100000，1 <= d

<= 100, 1 <= a[i] <= 100000。

输出一个数字，表示最小的操作次数，如果无解输出 -1。

示例 1

输入：
5
2
[3,5,7,1,9]
输出：
6

注意

最优解为全部变为 5，共 1 + 0 + 1 + 2 + 2 = 6 次。

C++代码

#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
//#define Max 100000;
/*
5
2
3 5 7 1 9
*/
using namespace std;

int Conversion(int a[], int n, int d);

int main()
{
    int Max = 100000;
    int n,d;
    int a[Max];
    cin >> n;
    cin >> d;
    for (int i = 0;i < n; i++)
    {
        cin >>a[i];
    }

    int answer = Conversion(a,n,d);

    cout << answer << endl;
    return 0;
}
int Conversion (int a[], int n, int d)
{
    int Max = 100000;
    int b[Max] = {0};
    int c[Max] = {0};
    int h[Max] = {0};  //取倍数
    int temp = a[0]%d;
    c[0] = a[0]/d;
    h[0] = c[0];
    for (int i = 1;i<n;i++)
    {
        if (a[i]%d == temp)
        {
            c[i] = a[i]/d;
            h[i] = c[i];
        }
        else{
            return -1;
        }
    }
    int temptime = h[0];

    for (int i=0; i<n-1; i++ )
    {
        for(int j = 0; j < n-i-1; j++)
        {
            if (h[j] > h[j+1])
            {
                int t = h[j];
                h[j] = h[j+1];
                h[j+1] = t;

            }
        }
    }
    int sum=0;
    temp = n/2;
    for (int i = 0; i<n ;i++){
        sum+=abs(h[i]-h[temp]);
    }
    return sum;
}