CodeForces - 1360H Binary Median(二分)

题目链接：点击查看

题目大意：给出一个 n 和 m ，初始时集合中含有 0 ~ 2^m - 1 共 2^m 个数，随后从中删去 n 个数，现在需要此时集合中的中位数

题目分析：一开始被字典序迷惑了，仔细想了一下发现，其实二进制下的字典序，和普通的排序没有区别，且 m 最大才为 60 ，所以可以将字符串转换为整数从而进行二分，因为多了删除这个条件，我们需要设计一下 check 函数然后寻找一下单调性

设中位数为 k ，换句话说我们需要找到集合中第 k 大的那个数，可以二分 mid ，每次遍历一遍这 n 个数，计算有多少个数小于等于mid 记为 cnt ，那么此时 mid 所代表的数就是第 mid - cnt 小的了，观察一下单调性：

以第二个样例为例，观察一下单调性，最上面一行的红色数字代表当前的数在数列中是第几小，可以分类讨论一下如何二分：

当 mid < k 时：选择右半段

当 mid > k 时：选择左半段

当 mid = k 时：选择左半段

然后实现就好了

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=110;LL a[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){string s;cin>>s;a[i]=0;for(int j=0;j<m;j++)a[i]=a[i]*2+(s[j]-'0');}LL mark=((1LL<<m)-n-1)/2;LL l=0,r=(1LL<<m)-1,ans;while(l<=r){LL mid=l+r>>1;int cnt=0;for(int i=1;i<=n;i++)if(mid>=a[i])cnt++;if(mid-cnt>=mark){ans=mid;r=mid-1;}elsel=mid+1;}for(int i=m-1;i>=0;i--)printf("%d",(ans>>i)&1);puts("");}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1360H Binary Median(二分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。