D. Max Median （二分、思维）

逃离我推掉我的手 2021-07-16 15:26 435阅读 0赞

[题目][Link 1]

从结果分析，答案必定是数组中的一个值，那么我们将值排个序开始二分。check的话，对于我们将要检查的值mid，将原数组中所有小于mid的值设为-1，大于等于mid的值设为1，对于一段区间看其中位数是否>=mid，只要看变化后该区间的总和，如果>0则其中位数>=mid。用一个前缀和sum记录即可，从k开始遍历（最小长度为k），假设遍历到了 k+3，那么sum\[k+3\]-sum\[0\] sum\[k+3\]-sum\[1\] … sum\[k+3\]-sum\[3\]都可以取用，我们想要使值尽可能大，只需取sum\[1—3\]中的最小值相减，用一个数组维护前面前缀和的最小值即可。

Code:

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int lst[Max], sum[Max], v[Max];
    int n, k;
    int check(int mid)
    { 
    	for (int i = 1;i <= n;i++)
    		if (lst[i] >= mid)sum[i] = sum[i - 1] + 1;
    		else sum[i] = sum[i - 1] - 1;
    	int mi = 0;
    	for (int i = k;i <= n;i++)
    	{ 
    		if (sum[i] - mi > 0)return 1;
    		mi = min(mi, sum[i - k + 1]);
    	}
    	return 0;
    }
    
    int main()
    { 
    	cin >> n >> k;
    	for (int i = 1;i <= n;i++) {  cin >> lst[i];v[i] = lst[i]; }
    	int l = 1, r = n;
    	sort(v + 1, v + 1 + n);
    	while (l < r)
    	{ 
    		int mid = (l + r + 1) / 2;
    		if (check(v[mid]))l = mid;
    		else r = mid - 1;
    	}
    	cout << v[l];
    }

[Link 1]: https://codeforc.es/problemset/problem/1486/D

发表评论取消回复

表情：

评论列表（有 0 条评论，435人围观）

还没有评论，来说两句吧...

相关阅读

相关【二分答案】CF803 D

感觉之前的\1900好简单 [Problem - D - Codeforces][] 题意： ![47e9ce79fee54c63a55acba3cac6e937.pn

客官°小女子只卖身不卖艺/ 2024年03月23日 22:41/ 0 赞/ 47 阅读

相关思维+贪心——cf1042D

/ 首先考虑从后往前计算lis，显然0的在很多情况下的贡献要大于1 如果遇上0，那么lis++，如果遇上1，那么cnt1++，并且用cnt1更新lis

一时失言乱红尘/ 2023年10月11日 09:09/ 0 赞/ 17 阅读

相关 CodeForces - 609D (二分！二分！)

D. Gadgets for dollars and pounds time limit per test 2 seconds memory limit per test

╰半夏微凉°/ 2022年05月29日 10:59/ 0 赞/ 231 阅读

相关 codeforces 159 D(几何二分)

[传送门][Link 1] 题意：给你n个点，问与x轴相切，并且包含这n个点的圆的最小半径是多少。思路：真是做的的怀疑人生。思路是首先判断点是否在一边。如果在一边一定

我就是我/ 2022年05月04日 23:58/ 0 赞/ 177 阅读

相关 C - Median(166C 思维+ 二分)

题目描述： A median in an array with the length of n is an element which occupies position

刺骨的言语ヽ痛彻心扉/ 2022年02月19日 10:53/ 0 赞/ 161 阅读

相关 Median

include <stdio.h> include <stdlib.h> include <math.h> define MAXSIZ

﹏ヽ暗。殇╰゛Y/ 2021年11月04日 13:32/ 0 赞/ 323 阅读

相关 D. Divide and Summarize(思维)

[题目][Link 1] 思路：其实想一想不难看出我们只需要将所有的情况得到的值存储起来，然后在之后的问询阶段判断是否有这个值就可以了。然后注意一下当值都相同时进行特殊判

「爱情、让人受尽委屈。」/ 2021年07月16日 18:07/ 0 赞/ 368 阅读

相关 1469D - Ceil Divisions （思维）

[题目][Link 1] 思路：首先对于1 2 3 4 . . . 2e5 我想啊，让 i=3 到 2e5-1的数全部 i/2e5 那么这些数就全为1了，1 2 1 1

淩亂°似流年/ 2021年07月16日 16:32/ 0 赞/ 264 阅读

相关 D. Max Median （二分、思维）

[题目][Link 1] 从结果分析，答案必定是数组中的一个值，那么我们将值排个序开始二分。check的话，对于我们将要检查的值mid，将原数组中所有小于mid的值设为-

逃离我推掉我的手/ 2021年07月16日 15:26/ 0 赞/ 436 阅读

相关 1199D - Welfare State（思维）

[题目][Link 1] 题意：对于n个公民，我们知道其一开始的各自的金钱。现在我们有两种操作：1.直接将各个钱数小于k的公民的钱数转变为k。2.将第p个人的钱数抓变为k

我就是我/ 2021年07月16日 15:04/ 0 赞/ 444 阅读