codeforces-1201 C Maximum Median

约定不等于承诺〃 2023-06-01 08:51 20阅读 0赞

二分查找的典型应用，寻找虚无的值代入测试

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 typedef long long ll;
     4 using namespace std;
     5 inline ll read()
     6 {
     7     ll ans = 0;
     8     char ch = getchar(), last = ' ';
     9     while(!isdigit(ch)) last = ch, ch = getchar();
    10     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    11     if(last == '-') ans = -ans;
    12     return ans;
    13 }
    14 inline void write(ll x)
    15 {
    16     if(x < 0) x = -x, putchar('-');
    17     if(x >= 10) write(x / 10);
    18     putchar(x % 10 + '0');
    19 }
    20 ll n,k; 
    21 ll a[200006];
    22 bool C(ll d)
    23 {
    24     ll line = a[n/2]+d;
    25     ll tmpk = k;
    26     tmpk -= d;
    27     _for(i,n/2+1,n)
    28         if(a[i]<line)
    29             tmpk -= line-a[i];
    30         else
    31             break;
    32     return tmpk>=0;
    33 }
    34 ll solve()
    35 {
    36     ll lb = 0,ub = 1000000002;
    37     while(ub - lb > 1)
    38     {
    39         ll mid =  lb+(ub-lb)/2;
    40         if(C(mid)) lb = mid;
    41         else ub = mid;
    42     }
    43     return lb;
    44 }
    45 int main()
    46 {
    47     n = read(),k = read();
    48     _for(i,0,n)
    49         a[i] = read();
    50     sort(a,a+n);
    51     ll rnt = solve();
    52     write(rnt+a[n/2]);
    53     return 0;
    54 }

转载于:https://www.cnblogs.com/Asurudo/p/11301711.html

发表评论取消回复

表情：

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

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

相关阅读

相关 codeforces-1201 C Maximum Median

二分查找的典型应用，寻找虚无的值代入测试 1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i

约定不等于承诺〃/ 2023年06月01日 08:51/ 0 赞/ 21 阅读

相关 codeforces D. Maximum Value

D. Maximum Value time limit per test 1 second memory limit per test 256 megabytes i

约定不等于承诺〃/ 2022年07月24日 09:16/ 0 赞/ 160 阅读

相关 Codeforces 276D. Little Girl and Maximum XOR（模拟）

A little girl loves problems on bitwise operations very much. Here's one of them. You a

ゞ浴缸里的玫瑰/ 2022年06月07日 13:16/ 0 赞/ 225 阅读

相关 Codeforces 276C Little Girl and Maximum Sum(线段树的区间更新)

The little girl loves the problems on array queries very much. One day she came across

客官°小女子只卖身不卖艺/ 2022年06月07日 13:16/ 0 赞/ 179 阅读

相关 CodeForces 144C

问题描述: A string t is called an anagram of the string s, if it is possible to rearrange l

亦凉/ 2022年06月04日 06:51/ 0 赞/ 177 阅读

相关 Codeforces 196D Lexicographically Maximum Subsequence（模拟+哈希）

You've got string s, consisting of only lowercase English letters. Find its lexicographi

￡神魔★判官ぃ/ 2022年06月02日 05:25/ 0 赞/ 142 阅读

相关 1201 字符串排序

字符串排序 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 输入3个字符串，按字典

布满荆棘的人生/ 2022年05月29日 00:35/ 0 赞/ 149 阅读

相关 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 赞/ 158 阅读

相关 Median

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

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

相关 CodeForces 455C

题意：给定N，M和Q，N表示有N个城市，M条已经修好的路，修好的路是不能改变的，然后是Q次操作，操作分为两种，一种是查询城市x所在的联通集合中，最长的路为多长。二是连接两个联

谁借莪１个温暖的怀抱￠/ 2021年10月18日 08:38/ 0 赞/ 237 阅读