东莞社保官方网站,php网页开发,峰峰信息港免费发布平台,驻马店住房和城乡建设厅网站给定一个长度为 N 的整数数列#xff1a;A1, A2, ... , AN。你要重复以下操作 K 次#xff1a; 每次选择数列中最小的整数#xff08;如果最小值不止一个#xff0c;选择最靠前的#xff09;#xff0c;将其删除。 并把与它相邻的整数加上被删除的数值。 输出 K 次操作后…给定一个长度为 N 的整数数列A1, A2, ... , AN。你要重复以下操作 K 次 每次选择数列中最小的整数如果最小值不止一个选择最靠前的将其删除。 并把与它相邻的整数加上被删除的数值。 输出 K 次操作后的序列。
输入格式
第一行包含两个整数 N 和 K。 第二行包含 N 个整数A1, A2, ... , AN。 对于 20% 的数据1 ≤ K N ≤ 10000。 对于 100% 的数据1 ≤ K N ≤ 5 × 1e50 ≤ 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 iostreamusing namespace std;
int k,n;
const int N10010;
#define INF 0x3f3f3f3f3f3f3f
typedef long long int;
typedef pairint, int pii;
int a[N];
bool st[N];void solve()
{cin kn;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 pos1; 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_queuepii, vectorpii, greaterpiiq;
#include iostream
#include queueusing namespace std;
int k,n;
const int N10010;
#define INF 0x3f3f3f3f3f3f3f
typedef long long int;
typedef pairint, int pii;
int a[N], l[N], r[N];
int st[N];void solve()
{cin n k;priority_queuepii, vectorpii, greaterpiiq;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();
}
