网站开发组岗位,石家庄定制网站建设,商标设计要求及规范,北京天津网站建设CF1486D Max Median
题意#xff1a;
给定一个长度为 n 的序列 a#xff0c;求所有长度 ≥k 的连续子序列中#xff0c;中位数的最大值。定义中位数是一个长度为 x 的序列升序排序后的第 ⌊x12⌋\left\lfloor\frac{x1}{2}\right\rfloor⌊2x1⌋位的值。
题解#xff1a…CF1486D Max Median
题意
给定一个长度为 n 的序列 a求所有长度 ≥k 的连续子序列中中位数的最大值。定义中位数是一个长度为 x 的序列升序排序后的第 ⌊x12⌋\left\lfloor\frac{x1}{2}\right\rfloor⌊2x1⌋位的值。
题解
我第一反应是二分去判断但是不知道该怎么判断中位数这个条件 题目中定义的中位数的排序后最中间的数假设中位数为mid也就是说有一半以上的数mid那二分不就好判断了我们二分mid值然后将所有小于mid的值赋为-1大于等于mid的赋值为1现在问题就是是否存在一个区间长度大于等于k的区间值0 我们用sum来记录赋值后的前缀和用minn[i]表示min(sum[j]),j∈[1,i]min(sum[j]),j∈[1,i]min(sum[j]),j∈[1,i]。这样就是判断sum[i]-sum[i-k]是否大于等于0
代码
// Problem: D. Max Median
// Contest: Codeforces - Codeforces Round #703 (Div. 2)
// URL: https://codeforces.com/contest/1486/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 2e5 9;
int a[maxn];
int n, k;
int b[maxn];
int sum[maxn];
int minn[maxn];
bool check(int x)
{for (int i 1; i n; i) {b[i] (a[i] x) ? 1 : -1;}minn[0] INF_int;for (int i 1; i n; i) {sum[i] sum[i - 1] b[i];minn[i] min(minn[i - 1], sum[i]);}minn[0]0;for (int i k; i n; i) {if (sum[i] - minn[i - k] 0)return 1;}return 0;
}
int main()
{//rd_test();cin n k;for (int i 1; i n; i) {cin a[i];}int l 0, r n;int ans -1;while (l r) {int mid l r 1;if (check(mid)) {ans mid;l mid;}elser mid - 1;}cout ans endl;//Time_test();
}
