Submission #1214171

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <functional>
#include <chrono>
#include <time.h>
using namespace std;

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

	long long ans = 0;

	vector<int>see(n);
	int minH = a[0];
	int cnt = 1;
	for (int i = 0; i < n; i++){
		if (minH < a[i]) {
			minH = a[i];
			cnt++;
		}
		see[i] = minH;
	}

	while (cnt > k) {
		int index = 0;
		vector<pair<int, int>>b;
		for (int i = 0; i < n- 1; i++) {
			if (see[i] < see[i + 1]) {
				b.push_back(make_pair(see[i + 1] - see[i], index));
				index = i + 1;
			}
		}
		sort(b.begin(), b.end());
		a[b[0].second] += b[0].first;
		ans += b[0].first;

		int minH = a[0];
		cnt = 1;
		for (int i = 0; i < n; i++) {
			if (minH < a[i]) {
				minH = a[i];
				cnt++;
			}
			see[i] = minH;
		}
		cerr << cnt << endl;
	}

	while (cnt < k) {
		vector<pair<int, int>>b;
		vector<int>bias(n);
		for (int i = n - 1; i > 0; i--) {
			if (i < n - 1)bias[i] = bias[i + 1];
			if (see[i] == see[i - 1]) {
				b.push_back(make_pair(see[i] + 1 + bias[i] + - a[i], n - i));
			}
			else if(see[i]-see[i-1]==1){
				bias[i]++;
			}
			else bias[i] = 0;
		}
		sort(b.begin(), b.end());
		a[n-b[0].second] += b[0].first - bias[n - b[0].second];
		ans += b[0].first - bias[n - b[0].second];

		int minH = a[0];
		cnt = 1;
		for (int i = 0; i < n; i++) {
			if (minH < a[i]) {
				minH = a[i];
				cnt++;
			}
			see[i] = minH;
		}
	}

	cout << ans << endl;

    return 0;
}

Submission Info

Judge Result