给定一个长度为 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();
}