题目描述
给定一个长度为 $n$ 的正整数数组 $a_1,a_2,…,a_n$。
请你对该数组进行 $k$ 次操作,每次操作具体如下:
- 如果数组中存在非零元素,则找到其中的最小非零元素 $x$,将其输出,并让数组中的所有非零元素都减去 $x$。
- 如果数组中不存在非零元素,则输出 $0$ 即可。
输入格式
第一行包含两个整数 $n,k$。
第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$。
输出格式
共 $k$ 行,其中第 $i$ 行输出第 $i$ 次操作需要输出的值。
数据范围
前四个测试点满足 $1 \le n \le 10$。
所有测试点满足 $1 \le n,k \le 10^5$,$1 \le a_i \le 10^9$。
输入样例1:
3 5
1 2 3
输出样例1:
1
1
1
0
0
输入样例2:
4 2
10 3 5 3
输出样例2:
3
2
算法
(暴力枚举) $O(n^2)$
write here…
时间复杂度
write here…
空间复杂度
write here…
C++ 代码
#include "bits/stdc++.h"
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N], s[N];
int n, k;
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int sum = 0, dd = 0;
for (int i = 1; i <= n; i++) {
while (a[i] - sum <= 0 && i <= n) i++; // 找到最小的非0元素
if (a[i] - sum > 0) {
s[++dd] = (a[i] - sum);
sum += a[i] - sum;
}
}
for (int i = 1; i <= k; i++) {
cout << s[i] << '\n';
}
return 0;
}
差分
排序之后记得去重 因为当两个数相等的时候 需要减去前面那个数 后面那个数就会变成0,下一次操作的时候要找到最小的非0元素 此时的这个0已经对答案没有任何价值 所以要首先去重
本题每次需要我们减去最小的非0元素,其实就是用当前元素-前一个元素
#include "bits/stdc++.h"
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, k;
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int len = unique(a + 1, a + n + 1) - a - 1;
for (int i = 1; i <= k; i++) {
if (i <= len) cout << a[i] - a[i - 1] << '\n';
else cout << 0 << '\n';
}
return 0;
}