时间限制	内存限制
`1000 ms`	`65536 KB`

# 题目描述

小 P 获得了 $n$ 种颜色各不相同的小球，每种颜色分别有 $a_1,a_2,⋯,a_n$ 个小球，之后小 P 将它们都放在了一个不透明袋子中。小 P 每次将从袋子中抽取 $k$ 个颜色各不相同的小球，并将抽到的小球放到袋子之外。当袋子中的小球不可能再被抽出时，抽取将结束。小 P 想知道，最后的袋子中每种小球最少剩多少个？

# 输入格式

第一行给出两个整数 $n,k$ 。其中， $0<n≤2×10^5$ ， $0<k≤10^9$ 。

第二行给出 $n$ 个整数，分别代表 $a_1,a_2,⋯,a_n$ 。其中 $0<a_i≤10^9$ 。

为降低难度，保证 $a_1≤a_2≤⋯≤a_n$ 。

# 输出格式

输出共一行。

第一行输出 $n$ 个数，分别为每种小球最少剩余个数。

对于每一行，第 $i$ 个数输出第 $i$ 种小球最少剩余个数，且每两个数之间用一个空格间隔。

# 输入样例 1

	5 4
	1 2 3 4 5

# 输出样例 1

0 0 0 1 2

# 输入样例 2

	5 8
	1 1 1 1 11

# 输出样例 2

1 1 1 1 11

# 题解：前缀和 + 贪心

首先我们可以显然地得出这两个结论：

当 $k > n$ 时，按原数量输出，因为没有小球能被拿走；
当 $k \le n$ 时，从少到多前 $n - k + 1$ 种颜色的小球最少剩余个数都是 $0$ ，因为我们可以拿它们中的任意一种颜色和最后的 $k - 1$ 种颜色小球组队取出，最后一个不剩。

关键是我们如何求出最后这 $k - 1$ 种颜色的小球呢？考虑这样一组样例：

	7 4
	3 5 9 14 20 40 60

对于第 $5$ 种颜色的小球，我们的目标是让它剩得最少，也就是要拿得尽量多，也就是要尽可能不触发停止拿球的条件，也就是我们要尽量拿多的那几堆球，防止一下子把某种颜色的球拿光。注意：我们在拿球的过程中还会改变球的数量，直接暴力模拟这个过程是不可行的，显然时间爆炸。我们模拟一下小样例，看看能否从中发现规律：

考虑第 $5$ 堆球，首先锁定后面两堆比它大的球，在它俩被拿完之前第 $5$ 堆一定被先拿完。所以我们只需要考虑另外一堆怎么取，很显然，这一堆可以随便从 $3 5 9 14$ 里面出，它们的总数为 $31$ ，大于 $20$ ，所以第 $5$ 堆球能被拿完。

考虑第 $6$ 堆球，此时情况复杂了一些，因为我们只能锁定最后一堆球作为它的 “灵魂伴侣”，还有两堆球只能从前面出。我们如何平均地取这两堆球，能更晚的结束呢？考虑这样的操作方式：

	3 5 9 14 20 40 60
	3 5 9 9 15 35 55
	3 5 5 5 7 27 47
	3 4 4 4 4 24 44
	3 3 3 3 3 22 42
	1 1 1 1 1 17 37
	0 0 0 0 1 15 35

其实我们就是想尽办法，把前 $5$ 堆球全取了！前 $5$ 堆球总共有 $51$ 个，我们能取出 $25$ 组来，所以第 $6$ 堆最少剩 $40 - 25 = 15$ 个。

同时从上面的模拟中我们不难看出，最后一堆球最少只能剩 $35$ 个。但是前 $6$ 堆球总共有 $91$ 个，按道理能够凑出 $30$ 组啊！这个时候我们要考虑到我们在求第 $6$ 组的时候，总有 $15$ 个球取不出来，其余的球完全可以随着第 $7$ 组取出来，所以总数减掉 $15$ ，再除以 $3$ ，就是最后一堆球能拿出来的最大个数了！

综上，我们在实现的时候维护两个前缀数组：一个是球数的前缀数组，一个是答案的前缀数组，然后就可以从小到大，线性地求出答案了！

时间复杂度： $O(n)$ 。

参考代码：

	#include <stdio.h>

	typedef long long ll;

	int n, k, a[200010], ans[200010];
	ll prefix[200010], prefixAns[200010];

	ll max(ll a, ll b)
	{
	return (a > b) ? a : b;
	}

	int main()
	{
	// freopen("L.in", "r", stdin);
	// freopen("L.out", "w", stdout);

	scanf("%d%d", &n, &k);

	for (int i = 1; i <= n; ++ i)
	{
	scanf("%d", &a[i]);
	prefix[i] = prefix[i - 1] + a[i];
	}

	if (k > n)
	{
	for (int i = 1; i <= n; ++ i)
	printf("%d ", a[i]);

	return 0;
	}

	for (int i = 1; i <= n - k + 1; ++ i)
	printf("0 ");

	for (int i = n - k + 2; i <= n; ++ i)
	{
	ans[i] = max(0, a[i] - (prefix[i - 1] - prefixAns[i - 1]) / (i - n + k - 1));
	prefixAns[i] = prefixAns[i - 1] + ans[i];
	printf("%d ", ans[i]);
	}

	return 0;
	}

前缀和贪心