Chocolate Monger codechef solution in c++

 

Chocolate Monger Problem Code: CM164364

Submit

Read problems statements in Mandarin Chinese, Russian, and Bengali as well.

There are n$n$ chocolates, and you are given an array of n$n$ numbers where the i$i$-th number Ai$A_i$ is the flavour type of the i$i$-th chocolate. Sebrina wants to eat as many different types of chocolates as possible, but she also has to save at least x$x$ number of chocolates for her little brother.

Find the maximum possible number of distinct flavour types Sebrina can have.

Input:

The first line contains an integer T$T$ --- the number of test cases.

The first line of each test case consists of two integers n$n$, x$x$ - The number of chocolates Sabrina has and the number of chocolates she has to save for her brother, respectively.

The second line contains n$n$ integers A1,…,An$A_1,\dots ,A_n$, where the i$i$-th chocolate has type Ai$A_i$.

Output:

For each test case, output a single integer denoting the maximum possible number of distinct chocolate flavours Sabrina can eat.

Constraints

1≤T≤10$1\le T\le 10$

1≤x≤n≤2⋅105$1\le x\le n\le 2\cdot {10}^5$

1≤Ai≤109$1\le A_i\le {10}^9$

Sum of n$n$ over all test cases do not exceed 2⋅105$2\cdot {10}^5$

Sample Input 1 

3
2 1
1 2
4 2
1 1 1 1
5 3
50 50 50 100 100

Sample Output 1 

1
1
2

Explanation

In the first test case, she can give any 1 chocolate to her brother and can have the other for herself resulting in 1 flavour type for Sebrina.

solution:

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long

void solve()
{
    ll n,x;
    cin>>n>>x;
    vector<ll> v(n);
    for(ll i=0;i<n;i++)
    {
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    ll s=v.size();
    if(s>n-x)
    {
        s=n-x;
    }
    cout<<s<<"\n";
}

int main() {
	int t;
	cin>>t;
	while(t--)
	{
	    solve();
	}
	return 0;
}