1088B Ehab and subtraction

墨蓝 2022-04-11 08:44 151阅读 0赞

B. Ehab and subtraction

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You're given an array aa. You should repeat the following operation kk times: find the minimum non-zero element in the array, print it, and then subtract it from all the non-zero elements of the array. If all the elements are 0s, just print 0.

Input

The first line contains integers nn and kk (1≤n,k≤105)(1≤n,k≤105), the length of the array and the number of operations you should perform.

The second line contains nn space-separated integers a1,a2,…,ana1,a2,…,an (1≤ai≤109)(1≤ai≤109), the elements of the array.

Output

Print the minimum non-zero element before each operation in a new line.

Examples

input

Copy

3 5
    1 2 3

output

Copy

1
    1
    1
    0
    0

input

Copy

4 2
    10 3 5 3

output

Copy

3
    2

Note

In the first sample:

In the first step: the array is \[1,2,3\]\[1,2,3\], so the minimum non-zero element is 1.

In the second step: the array is \[0,1,2\]\[0,1,2\], so the minimum non-zero element is 1.

In the third step: the array is \[0,0,1\]\[0,0,1\], so the minimum non-zero element is 1.

In the fourth and fifth step: the array is \[0,0,0\]\[0,0,0\], so we printed 0.

In the second sample:

In the first step: the array is \[10,3,5,3\]\[10,3,5,3\], so the minimum non-zero element is 3.

In the second step: the array is \[7,0,2,0\]\[7,0,2,0\], so the minimum non-zero element is 2.

题意：给了一个a数组，需要执行k个步骤，每次找出最小的那个非0数，让所有非0数减去这个最小数。如果所有数为0 ，就打印0.

题解：大体思路是对数组排个序，然后k次upper\_bound(二分查找，找出第一个大于num的数的下标x），输出a\[x\]-num,如果a\[x\]不大于0，就跳出，输出剩余k个0,break后，如果while（k--）的话要特别注意k的值，k--会可能跳到负数，死循环，超时，这步菜鸡操作，昨晚把自己都写自闭了，才找到原因....

c++：

#include<bits/stdc++.h>
    using namespace std;
    int a[100010],n,k,num;;
    int main()
    {
        cin>>n>>k;
        for(int i=0; i<n; i++)
            cin>>a[i];
        sort(a,a+n);
        while(k--)
        {
            int x=upper_bound(a,a+n,num)-a;
            if(a[x]>0) cout<<a[x]-num<<endl;
            else
            {
                 cout<<0<<endl;
                 break;
            }
            num+=a[x]-num;
        }
        while(k--&&k>=0)
        {
            cout<<0<<endl;
        }
        return 0;
    }

python：

n,k = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    i,m = 0,0
    while k:
        while a[i] - m <= 0 and i<n-1: i+=1
        print(a[i]-m)
        m+=a[i]-m
        k-=1