题目描述
给定一个长度为 N 的整数数列:A1, A2, ... , AN。你要重复以下操作 K 次:
每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。
并把与它相邻的整数加上被删除的数值。
输出 K 次操作后的序列。
输入格式
第一行包含两个整数 N 和 K。
第二行包含 N 个整数,A1, A2, ... , AN。
对于 20% 的数据,1 ≤ K < N ≤ 10000。
对于 100% 的数据,1 ≤ K < N ≤ 5 × 105,0 ≤ Ai ≤ 108。
输出格式
输出 N − K 个整数,中间用一个空格隔开,代表 K 次操作后的序列。
输入样例 复制
5 3
1 4 2 8 7
输出样例 复制
17 7
数据范围与提示
数列变化如下,中括号里的数是当次操作中被选择的数:
[1] 4 2 8 7
5 [2] 8 7
[7] 10 7
17 7
#include<bits/stdc++.h>
using namespace std;
typedef pair<long long, pair<long long, long long>> heap;
priority_queue <heap, vector<heap>, greater<heap>> q;
int main() {
long long N, K, start = 0;
long long A[500010] = {0};
long long visit[500010] = {0};
long long next[500010] = {0};
long long before[500010] = {0};
long long times[500010] = {0};
long long min[500010] = {0};
cin >> N >> K;
for (long long i = 1; i <= N; i ++) {
cin >> A[i];
visit[i] = 1;
}
for (long long i = 1; i <= N; i ++) {
next[i] = i + 1;
before[i] = i - 1;
}
for (long long i = 1; i <= N; i ++) {
q.push(make_pair(A[i], make_pair(i, 0)));
}
while (q.size()) {
if (start == K) {
break;
}
while (q.top().second.second != times[q.top().second.first]) {
q.pop();
}
long long index = q.top().second.first;
long long value = q.top().first;
q.pop();
if (min[index]) {
continue;
}
min[index] = 1;
if (visit[next[index]]) {
A[next[index]] += value;
q.push(make_pair(A[next[index]], make_pair(next[index], ++times[next[index]])));
}
if (visit[before[index]]) {
A[before[index]] += value;
q.push(make_pair(A[before[index]], make_pair(before[index], ++times[before[index]])));
}
next[before[index]] = next[index];
before[next[index]] = before[index];
start++;
}
start = 1;
while (min[start]) {
start++;
}
while (start != N + 1) {
cout << A[start] << " ";
start = next[start];
}
return 0;
}
补充:
这里队列采用的存储格式为(值,索引号,以及已经找出的最小值的个数)
然后每次循环,将最小值pop,并把值加给左右两个节点,同时将新节点push进队列
一定要修改next和before索引数组,这两个数组是寻找最小值左右两节点的关键
最后输出时,找到第一个不是作为最小值而删除的节点,然后不断遍历next数组寻找下一个