贝壳找房移山(简单/中等)

题目链接

贝壳找房移山(简单)
贝壳找房移山(中等)

题解

中档题。由于每次移山是将连续的一段山顶移除1个单位的高度,只需提取出所有的山顶与山谷的高度来减少运算量。
之后每次贪心找出并抹去一个消耗最少的山顶即可。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#define maxxx(a,b) (a>b?a:b)
#define ll long long
using namespace std;
ll n, k,t;
ll a;
vector<ll> high;
int main() {
    cin >> t;
    for (ll q = 1; q <= t; q++) {
        cin >> n >> k;
        ll last = 0, ans = 0;
        high.clear();
        bool which = true;//true 找峰,false找谷底
        high.push_back(0);
        for (ll i = 1; i <= n; i++) {
            cin >> a;
            if (which) {
                if (a < last) {
                    high.push_back(last);
                    which = false;
                }
            }
            else {
                if (a > last) {
                    high.push_back(last);
                    which = true;
                }
            }
            last = a;
        }
        if (which == true) {
            high.push_back(last);
            high.push_back(0);
        }
        else
            high.push_back(0);
        ll numofsf = high.size() / 2;
        for (ll i = 1; i <= numofsf-k; i++) {
            ll willdel = 1;
            for (ll j = 1; j <= high.size() / 2; j++) {
                if (high[j * 2 - 1] - (maxxx(high[j * 2 - 2], high[j * 2])) < high[willdel] - maxxx(high[willdel - 1], high[willdel + 1]))
                    willdel = j * 2 - 1;
            }
            if (high[willdel + 1] > high[willdel - 1]) {
                ans += high[willdel] - high[willdel + 1];
                high.erase(high.begin() + willdel);
                high.erase(high.begin() + willdel);
            }
            else {
                ans += high[willdel] - high[willdel - 1];
                high.erase(high.begin() + willdel-1);
                high.erase(high.begin() + willdel-1);
            }
        }
        cout << ans<<endl;
    }
}

标签: implementation, greedy

添加新评论