Как найти минимальную стоимость?

Question

Я пытаюсь решить проблему, заключающуюся в поиске минимальной стоимости. Задача может быть сформулирована следующим образом: для каждого здания и для каждого здания указана его высота и стоимость. Теперь задача состоит в том, чтобы найти минимальную стоимость, чтобы все здания становятся равными по высоте. Каждое здание можно рассматривать как вертикальную кучу кирпичей, где каждый кирпич можно добавлять или удалять с затратами, связанными с этим зданием.

Например: Скажем, есть n = 3 здания с высотой 1,2,3 и стоимостью 10 100 000 соответственно.

Здесь минимальная стоимость будет равна 120.

Вот ссылка на проблему:

http://www.spoj.pl/problems/KOPC12A/

Очевидный ответ будет состоять в том, чтобы найти стоимость, связанную с каждой из высот для всех зданий, а затем дать на выходе минимальную стоимость из них. Это O (n ^ 2).

В поисках лучшего решения я попытался найти высоту с минимальным значением соотношения высоты / стоимости. Затем все здания должны быть равны этой высоте, рассчитать стоимость и дать в качестве результата. Но это дает мне неправильный ответ , Вот моя реализация:

На основании приведенных ниже ответов я обновил свой код с использованием средневзвешенного значения, но все еще не работает. Он дает мне неправильный ответ.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>

using namespace std;

long long fun(int h[],int c[],int optimal_h,int n){
    long long res=0;
    for(int i=0;i<n;i++){
        res += (abs(h[i]-optimal_h))*c[i];
    }   
    return res;
}

int main()
{
    int t;
    cin>>t;
    for(int w=0;w<t;w++){
        int n;
        cin>>n;
        int h[n];
        int c[n];
        int a[n];
        int hh[n];
        for(int i=0;i<n;i++){
            cin>>h[i];
            hh[i]=h[i]; 
        }
        sort(hh,hh+n);
        for(int i=0;i<n;i++)
            cin>>c[i];

        long long w_sum=0;  
        long long cost=0;

        for(int i=0;i<n;i++){
            w_sum += h[i]*c[i];
            cost += c[i];   
        }

        int optimal_h;
        if(cost!=0){
            optimal_h=(int)((double)w_sum/cost + 0.5);
            if(!binary_search(hh,hh+n,optimal_h)){
                int idx=lower_bound(hh,hh+n,optimal_h)-hh;
                int optimal_h1=hh[idx];
                int optimal_h2=hh[idx-1];
                long long res1=fun(h,c,optimal_h1,n);
                long long res2=fun(h,c,optimal_h2,n);
                if(res1<res2)
                    cout<<res1<<"\n";   
                else
                    cout<<res2<<"\n";
            }
            else{
                long long res=fun(h,c,optimal_h,n);
                cout<<res<<"\n";
            }

        }
        else
            cout<<"0\n";
    }

    return 0;
}

Есть идеи, как это решить?

Answer 1

Попробуйте думать о высотах как о значениях, а затраты как об уверенности, значимости.

Простое средневзвешенное значение должно помочь в этом:

costsum=0;
weightedsum=0;
for(int i=0; i<n; ++i)
{
   costsum += c[i];
   weightedsum += h[i]*c[i];
}

optimalheight = round(double(weightedsum)/costsum);

Затем посчитайте стоимость, зная оптимальную высоту:

cost=0;
for(int i=0; i<n; ++i)
   cost += c[i] * abs(h[i] - optimalheight);

Answer 2

Недавно я столкнулся с подобным вопросом, небольшая разница в том, что в моем вопросе можно только добавлять этажи в здание, но вы не можете его удалить. Но идея должна быть похожей. Не стесняйтесь оставлять мне любые комментарии или вопросы.

Я думаю, что один хороший способ подойти к этому вопросу: Сначала отсортируйте входные данные, обычно это можно сделать с помощью вызовов API, встроенных в язык, в Java я использовал Arrays.sort (). Обычно это nLog (n) сложность времени. После сортировки мы можем поддерживать окно размера m, внутри окна мы можем вычислить минимальную стоимость для каждого окна, в то время как мы перемещаем окно от начала до конца, мы вычисляем и обновляем глобальную минимальную стоимость. Вот реализация:

    static long minFloors(long[] buildings, int m) {
        //sort buildings
        Arrays.sort(buildings);
        //maintain a window of size m, compute the minCost of each window, update minCost along the way as the final result
        long minCost = Long.MAX_VALUE;
        for(int i = 0; i <= buildings.length-m; i++){
            long heightToMatch = buildings[i+m-1];
            if(heightToMatch == buildings[i]) return 0;//if the last building's height equals the first one, that means the whole window if of the same size, we can directly return 0
            long thisCost = 0; 
            for(int j = i+m-1; j >= i; j--){
                thisCost += heightToMatch - buildings[j];
            }
            minCost = Math.min(minCost, thisCost);
        }
        return minCost;
    }

Также я поделился своим решением здесь: Вопрос Space Rock

Answer 3

Вот решение, которое требует сортировки высоты здания (я собираюсь предположить, от самой низкой до самой высокой). Если данные уже отсортированы, то они должны выполняться за время O (N).

Пусть k будет высотой всех зданий, поэтому мы хотим найти оптимальное k. Стоимость корректировки всех этих зданий определяется как:

    M = Sum(|k-hj|cj, j from 0 to N).

Теперь, поскольку они отсортированы, мы можем найти индекс i такой, что для всех j <= i, hj <= k и для всех j> i, hj> k. Это означает, что мы можем переписать наше уравнение стоимости следующим образом:

    M = Sum((k-hj)cj, j = 0 to i) + Sum((hj-k)cj, j = i+1 to N).

Теперь мы будем перебирать значения k между самым коротким и самым высоким зданием, пока не найдем здание с наименьшей стоимостью (далее мы увидим, что нам не нужно проверять каждое из них) Расчет стоимости на каждой итерации - это N операций, поэтому вместо этого мы найдем рекурсивное определение нашей функции стоимости:

    M(k+1) = Sum((k+1-hj)cj, j = 0 to p) + Sum((hj-k-1)cj, j = p+1 to N).

Мы можем вычесть термины '1' из сумм, чтобы получить:

    M(k+1) = Sum((k-hj)cj, j = 0 to p) + Sum((hj-k)cj, j = p+1 to N) + Sum(cj, j = 0 to p) - Sum(cj, j = p+1 to N).

Теперь p - это новый i, и есть 2 возможных случая: p = i или p = i + 1. если p = i:

    M(k+1) = M(k) + Sum(cj, j = 0 to p) - Sum(cj, j = p+1 to N)

и если p = i + 1

    M(k+1) = M(k) + Sum(cj, j = 0 to p) - Sum(cj, j = p+1 to N) + 2(k+1 - h(i+1))c(i+1).

В случае, когда p = i, мы можем фактически найти M (k + m) непосредственно из M (k), потому что на каждой итерации мы добавляем только постоянный член (постоянный в терминах k, то есть), поэтому, если p = я:

    M(k+m) = M(k) + m(Sum(cj, j = 0 to p) - Sum(cj, j = p+1 to N)).

Это означает, что наша функция образует прямую линию между итерациями, где i является постоянной величиной. Поскольку нас интересует, когда наша функция переходит от уменьшения к увеличению, это не может произойти в середине всех этих итераций. Это может произойти только при увеличении i (p = i + 1) или на первом шаге после (поскольку линия отличается от линии, ведущей к ней). Из того, что здесь до сих пор, алгоритм будет выглядеть примерно так:

1. Сортировать высоты при необходимости (O (NlogN))
2. Инициализируйте ваши 4 суммы (две суммы в M (k) и две дополнительные суммы, введенные в M (k + 1)) (O (N))

3. итерируйте по своим высотам, как это (O (N)), находя минимальное значение по ходу:

   -Увеличить k до высоты следующего самого высокого здания минус единица (используя M (k + m)) и посмотреть, представляет ли это новый минимум

   -Увеличить k на единицу, изменив значения i, и посмотреть, соответствует ли это новому минимуму

4. Распечатайте ответ.

Здесь возможны некоторые другие оптимизации, о которых я пока не особо задумывался. Очевидным является не пересчитывать ваши суммы, когда я меняюсь.

Я извиняюсь, если математику трудно читать, я новичок в StackOverflow и не выяснил все возможные форматы.

У меня нет кода для поддержки этого, поэтому я надеюсь, что это достаточно хорошо.