D. Max Median(Codeforces Round #703 (Div. 2)题解)
2021/5/20 10:31:00
本文主要是介绍D. Max Median(Codeforces Round #703 (Div. 2)题解),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接:D. Max Median
思路:二分答案,因为直接找的话肯定是不行的,因为区间共有\(\sum_{i=1}^{n}{i}\)复杂度\(\theta(n^2)\),所以我们需要思考,既然暴力查询不可以,我们逆向思维,给你一个数,你是否能在\(\theta(n)\)的时间内求出该数组有一段区间中位数要大于等于该数,这个判断是能够实现的,这是因为如果一个数能做中位数,那么一段区间内大于等于该数的数量一定大于等于\(\lceil \frac{n+1}{2} \rceil\),我们可以把原数组小于该数的看做-1,大于等于该数的看做1,然后求一遍前缀和,然后我们发现题意就变为求一段大于等于k区间内\(sum\)的最大值,如果最大值大于0,那么就是1的数量要比-1的数量多,所以该答案被允许,我们可以利用定右端点的方式,首先右端点设为k,那么显然答案只有[1,k]这一个,这时最优左端点是1,那么如果我们右端点向右移动1格,那么现在左端点的选择又多了一个,那就是2这个点(即[2,k+1])令区间满足最大就是令左端点对应的前缀和值最小,就这样一直右移右端点,每次进入决策集合的只有一个点,我们可以求最小值来进行决策。然后的工作就好做了,二分答案判断是否合法。
\(Code:\)
/* -*- encoding: utf-8 -*- ''' @File : D.cpp @Time : 2021/05/19 19:52:36 @Author : puddle_jumper @Version : 1.0 @Contact : 1194446133@qq.com ''' # here put the import lib*/ #include<set> #include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<cstdlib> #include<map> #include<algorithm> #include<vector> #include<queue> #define ch() getchar() #define pc(x) putchar(x) #include<stack> #include<unordered_map> #define rep(i,a,b) for(auto i=a;i<=b;++i) #define bep(i,a,b) for(auto i=a;i>=b;--i) #define lowbit(x) x&(-x) #define ll long long #define ull unsigned long long #define pb push_back #define mp make_pair #define PI acos(-1) using namespace std; template<typename T>void read(T&x){ static char c; static int f; for(c=ch(),f=1; c<'0'||c>'9'; c=ch())if(c=='-')f=-f; for(x=0; c>='0'&&c<='9'; c=ch())x=x*10+(c&15); x*=f; } template<typename T>void write(T x){ static char q[65]; int cnt=0; if(x<0)pc('-'),x=-x; q[++cnt]=x%10,x/=10; while(x) q[++cnt]=x%10,x/=10; while(cnt)pc(q[cnt--]+'0'); } const int N = 2e5+10; int n ,k; int a[N],sum[N]; bool check(int p){ rep(i,1,n){ sum[i] = sum[i-1]; if(a[i]>=p)sum[i]++; else sum[i]--; } int idx = 0; rep(i,k,n){ int now = sum[i] - sum[idx]; if(now > 0)return true; if(sum[i-k+1]<=sum[idx])idx = i-k+1; } // if(sum[n]-sum[idx]>0)return true; return false; } void solve(){ read(n);read(k); int l = 9999999,r = -1; rep(i,1,n){ read(a[i]);l = min(l,a[i]);r = max(r,a[i]); } while(l<r){ int mid = l + r + 1 >> 1; if(check(mid))l = mid; else r = mid - 1; } write(r);pc('\n'); } signed main(){solve();return 0; }
这篇关于D. Max Median(Codeforces Round #703 (Div. 2)题解)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享