修塔游戏题解

思路，对高度为h的塔，都假定比它高和矮的塔向它靠拢，计算出最终达到共有k座高度为h的塔的最少操作次数，并最终计算所有高度的操作次数中的最小次数即为答案。
我使用map来保存每种高度的塔的数量。使用去重的vector保存排好序的塔。
同时使用四个vector保存计算所需要的变量。对于每一个高度的塔，算出左边都变为它的高度总共使用的操作次数，使用dp的方法累积计算，右边同理。其次还要计算每一个高度的塔左右两侧不同高度塔的数量。
最后只用一次遍历塔的数组，就能用这些状态算出每一种高度最少操作次数。
关键：每一种高度的塔的左侧操作次数是左侧都变为前一个高度的塔（towsLeftOp[i-1]）再变为只比它高度少1的塔(+(tows[i]-tows[i-1]-1)*towsLeftNums[i-1])。右侧同理。
比较每一种高度的塔数量和它左右的塔数量，可以计算出最小需要发生变化的次数。

#include <algorithm>
#include <iostream>
#include <vector>
#include<map>
using namespace std;

int main()
{
    vector<int> tows;
    vector<int> towsLeftNums;
    vector<int> towsRightNums;
    vector<int> towsLeftOp;
    vector<int> towsRightOp;
    map<int,int>tmap;
    int n=0;int k=0;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        int t=0;cin>>t;
        tows.push_back(t);
        tmap[t]++;
    }
    sort(tows.begin(),tows.end());
    tows.erase(unique(tows.begin(), tows.end()), tows.end());
    for(int i=0;i<tows.size();i++)
    {
        if(i==0) 
            {
                towsLeftOp.push_back(0);
                towsLeftNums.push_back(tmap[tows[i]]);
            }
        else
        {
            towsLeftNums.push_back(towsLeftNums[i-1]+tmap[tows[i]]);
            int op=(tows[i]-tows[i-1])*towsLeftNums[i-1]+towsLeftOp[i-1];
            towsLeftOp.push_back(op);
        }    
    }
    for(int i=tows.size()-1;i>=0;i--)
    {
        if(i==tows.size()-1) 
        {
            towsRightOp.push_back(0);
            towsRightNums.push_back(tmap[tows[i]]);
        }

        else
        {
            towsRightNums.push_back(towsRightNums[tows.size()-i-2]+tmap[tows[i]]);
            int op=(tows[i+1]-tows[i])*towsRightNums[tows.size()-i-2]+towsRightOp[tows.size()-i-2];
            towsRightOp.push_back(op);
        }    
    }
    reverse(towsRightOp.begin(),towsRightOp.end());
    reverse(towsRightNums.begin(),towsRightNums.end());



    vector<int> ops;
    for(int i=0;i<tows.size();i++)
    {
        int leftOp=0;
        int rightOp=0;
        if(i>0)
        leftOp=towsLeftOp[i-1]+(tows[i]-tows[i-1]-1)*towsLeftNums[i-1];
        if(i<tows.size()-1)
        rightOp=towsRightOp[i+1]+(tows[i+1]-tows[i]-1)*towsRightNums[i+1];
        int leftTows=0;
        if(i>0)
        leftTows=towsLeftNums[i-1];
        int self=tmap[tows[i]];
        int rightTows=0;
        if(i<tows.size()-1)
        rightTows=towsRightNums[i+1];
        if(self>=k)
        {
            ops.push_back(0);
        }
        else
        {
            int times=0;
            if(self+leftTows<k&&self+rightTows<k)
            {
                times=leftOp+rightOp+k-self;
            }
            else if(self+leftTows>=k)
            {
                times=leftOp+k-self;
                if(self+rightTows>=k)
                {
                int times2=rightOp+k-self;
                if(times2<times)
                times=times2;
                }
            }
            else if(self+leftTows<k)
            {    
                times=rightOp+k-self;
            }
            ops.push_back(times);
        }

    }
    cout<<*min_element(ops.begin(),ops.end());
}