Codeforces Round #706 (Div. 2)B. Max and Mex

題目

題目大意

剛開始給你n個不同的數，k次詢問每次求在該序列中已存在的最大的數和不存在的最小的數（大于等于零）的和除以2想上取整在插入原序列中，經過k次詢問后求序列中有多少個不同的元素。

輸入樣例

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

輸出樣例

4 4 3 5 3

解題思路

題目給你k的范圍最大到1e9，那么肯定就是有規律可尋的，一共有三種情況不同元素個數不變，不同元素個數加一，不同元素個數加k，第一種情況就是原序列元素中從0到已給的最大元素這個區間里有元素空缺，那么且空缺元素加上最大元素值除2想上取整得到的元素在原序列已存在，同理剩下k-1次也是這樣子重復插入同一個已存在的元素，而第二種就是原序列元素中從0到已給的最大元素這個區間里有元素空缺，那么且空缺元素加上最大元素值除2想上取整得到的元素在原序列不存在，同理剩下k-1次也是這樣子重復插入同一個元素，即不同元素加1，最后一種情況就是從0到已給的最大元素這個區間里沒有元素空缺，那么你去最小值就是已給的最大元素+1，然后的得到的結果就是已給的最大元素+1，然后k-1次重復這樣的操作，每次都會插入不同的元素。

通過代碼

#include <bits/stdc++.h> using namespace std; #define ll long long #define sl(n) scanf("%lld",&n) #define pl(n) printf("%lld",n) #define pE printf("\n") #define ull unsigned long long #define pb push_back #define pre(n) for(ll i=1;i<=n;i++) #define rep(n) for(ll i=n;i>=1;i--) #define pi pair<ll,ll> int main() {ll t,i,j,n,k,m;sl(t);while(t--){m=-1;sl(n),sl(k);map<ll,ll>a;pre(n){sl(j);m=max(m,j);a[j]++; }if(!k){pl(n);pE;continue;}bool flag=false ;ll temp ;for(i=0;i<=m;i++){if(a[i]==0){temp=i;flag = true;break;}}if(!flag){pl(n+k);pE;continue;}if(a[(temp+m+1)/2]==0)pl(n+1);else pl(n);pE; }return 0; }

總結

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

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