2023河南萌新联赛第（三）场：郑州大学（两个题目）

1.入门mex

重点

• 一些数字的mex是从0往上枚举，第一个没出现的数字。
• 请你回答选最多k个数字，mex最大是多少

既然从0开始枚举，那么应该是最小，那么最大是什么？
经过自己的考虑，给出一个样例，0 1 1 2 3 4 选三个的话，正常考虑选前三小，那么就不满足最大的mex了，所以相同的就留下一个，给出代码

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N],b[N];
int ans;
int n,k;
int cnt;
int main()
{cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);if(a[1]>0)cout<<"0";else {for(int i=1;i<n;i++){if(a[i+1]-a[i]!=0)b[cnt++]=a[i];if(cnt==k)break;}for(int i=0;i<k;i++){if(b[i+1]-b[i]>1){ans=b[i]+1;break;}}if(ans==0)cout<<b[k-1]+1;else cout<<ans;}return 0;
}

2.泰拉瑞亚

• 这个就一点，a[i]>b[i]，这种情况考虑一下就行

#include<bits/stdc++.h>
using namespace std;
const int N=100005;int a[N],b[N];
long long  ans,sum;
int n,h,kk=-1;
bool cmp(int x,int y)
{return x>y;
}
int main()
{cin>>n>>h;for(int i=0;i<n;i++){cin>>a[i]>>b[i];}sort(a,a+n,cmp);sort(b,b+n,cmp);for(int i=0;i<n;i++){if(a[0]>=b[i]){kk=i;break;}else sum+=b[i];}	
//	cout<<kk<<endl;
//	cout<<sum<<endl;if(kk==-1){if(h-sum>0){h=h-sum;if(h%a[0]==0)ans=n+(h/a[0]);else ans=n+(h/a[0])+1;cout<<ans;}else{int k=0;while(h>0){h-=b[k];k++;}cout<<k;}	}else {h=h-sum;if(h%a[0]==0)ans=kk+(h/a[0]);else ans=kk+(h/a[0])+1;cout<<ans<<endl;}return 0;
}