原題鏈接

原題大意：
給出一個長度為n的序列，你可以進行k次操作，問操作后序列內有多少個不同的數，操作如下： 序列中最小未出現的數記為a
序列中最大的數記為b 添加（a+b）/2向上取整到序列中

輸入格式
輸入由多個測試用例組成。第一行包含單個整數t(1≤t≤100)-測試用例的數量。測試用例的描述如下。

每個測試用例的第一行包含兩個整數n，k(1≤n≤105，0≤k≤109)-多集S的初始大小以及需要執行的操作數量。

每個測試用例的第二行包含n個不同的整數a1、a2、…。，an(0≤ai≤109)-初始多集中的數字。

可以保證所有測試用例上的n之和不超過105。

輸出格式
對于每個測試用例，在完成k個操作后，打印S中不同元素的數量。

Example
input
5
4 1
0 1 3 4
3 1
0 1 4
3 0
0 1 4
3 2
0 1 2
3 2
1 2 3
output
4
4
3
5
3

---

首先，我們可以知道每次操作添加的數不可能為a，因為b一定存在，且大于1.
所以每次操作添加的值一樣。

但是還有一種情況，a=b+1,即所有數相鄰，這樣a會等于最大值加一，每次操作添加的值就會發生改變了，每次操作必然添加一個原序列中沒有的數

AC代碼：

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e5+3; map<ll,int > s; int main(){int T;scanf("%d",&T);while(T--){int n,k;s.clear();scanf("%d %d",&n,&k);ll a,b=0;int sum=0;for(int i=1;i<=n;++i){ll x;scanf("%lld",&x);if(s[x]==0)sum++;s[x]++;b=max(b,x);}a=b+1;for(int i=0;i<=b;++i)if(s[i]==0){a=i;break;}if(a<b&&k!=0){if(!s[(a+b+1)/2])sum++;}else sum+=k;printf("%d\n",sum);} return 0; }

總結

以上是生活随笔為你收集整理的Codeforces Round #706 (Div. 2) B. Max and Mex的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。