蓝桥杯-整数删除

给定一个长度为 N 的整数数列：A1, A2, ... , AN。你要重复以下操作 K 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。
并把与它相邻的整数加上被删除的数值。
输出 K 次操作后的序列。

输入格式

第一行包含两个整数 N 和 K。
第二行包含 N 个整数，A1, A2, ... , AN。
对于 20% 的数据，1 ≤ K ＜ N ≤ 10000。
对于 100% 的数据，1 ≤ K ＜ N ≤ 5 × 1e5，0 ≤ Ai ≤ 1e8。

输出格式

输出 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 <iostream>using namespace std;
int k,n;
const int N=10010;
#define INF 0x3f3f3f3f3f3f3f
typedef long long int;
typedef pair<int, int> pii;
int a[N];
bool st[N];void solve()
{cin >> k>>n;for (int i = 0; i < n; i++){cin >> a[i];}for (int  i = 0; i < k; i++){int minNum = INF;int pos = -1;for (int j = 0; j < n; j++){if (minNum > a[j]&&!st[j]){minNum = a[j];pos = j;}}st[pos] = true;for (int j = pos+1; j < n; j++){if (!st[j]){a[j] += minNum;break;}}for (int  j = pos-1; j >0; j--){if(!st[j]){a[j] += minNum;break;}}}for (int i = 0; i < n; i++){if (!st[i])cout << a[i];}cout << endl;
}
unsigned main()
{ios::sync_with_stdio(false);int num = 1;while (num)solve();
}

最优解

小根堆求解

#include <queue>关键代码stl

priority_queue<pii, vector<pii>, greater<pii>>q;

#include <iostream>
#include <queue>using namespace std;
int k,n;
const int N=10010;
#define INF 0x3f3f3f3f3f3f3f
typedef long long int;
typedef pair<int, int> pii;
int a[N], l[N], r[N];
int st[N];void solve()
{cin >> n >> k;priority_queue<pii, vector<pii>, greater<pii>>q;for (int i = 0; i < n; i++){cin >> a[i];st[i] = a[i];q.push({ a[i],i });l[i] = i - 1;r[i] = i + 1;if (i == n)r[i] = -1;}while (k){pii t = q.top();q.pop();if (t.first != st[t.second]){q.push({ st[t.second] , t.second});continue;}k--;int pos = t.second;if (l[pos] >= 0){st[l[pos]] += t.first;r[l[pos]] = r[pos];}if (r[pos] >= 0){st[r[pos]] += t.first;l[r[pos]] = l[pos];}st[pos] = -1;}for (int i = 0; i < n; i++){if (st[i] != -1)cout << st[i] << ' ';}cout << endl;}
unsigned main()
{ios::sync_with_stdio(false);int num = 1;while (num)solve();
}