本文最后更新于 723 天前,其中的信息可能已经有所发展或是发生改变。
Origional Link
思想:
- 贪心,模拟。
- 首先对数组进行从小到大排序,再找到第一个
a[idx] != 0
的位置。
- 对于每次询问,以
base
记录当前数组已经减去的总值,判断时应当计算当前元素与 base
的差值。
- 若
a[idx] - base > 0
说明需要将后续所有元素减去值 a[idx] - base
,将该值加和到 base
中。
- 若
a[idx] - base == 0
说明当前元素在操作后已经为 0,则需要向后寻找操作后不为 0 的元素。
- 由于贪心的思想,数组中的所有的元素一定满足 a[idx]−base≤a[idx+1]−base。
- 最后当
idx
不能再向后移动时,说明全部元素经操作后都变为了 0。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 1e6 + 3; |
| |
| int a[N]; |
| |
| void solve(){ |
| int n, k; cin >> n >> k; |
| for(int i = 0; i < n; i ++) cin >> a[i]; |
| sort(a, a + n); |
| int idx = 0; while(a[idx] == 0 && idx < n) idx ++; |
| int base = 0; |
| while(k --){ |
| while(a[idx] - base == 0 && idx < n) idx ++; |
| if(a[idx] - base > 0){ |
| cout << a[idx] - base << endl; |
| base += a[idx] - base; |
| } |
| else cout << 0 << endl; |
| } |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |