$CF949D\ Curfew$ 二分/贪心

时间：2023-03-09 09:13:27
$CF949D\ Curfew$ 二分/贪心

正解:二分/贪心

解题报告:

传送门$QwQ$

首先这里是二分还是蛮显然的?考虑二分那个最大值,然后先保证一个老师是合法的再看另一个老师那里是否合法就成$QwQ$.

发现不太会搞这个合不合法的所以咕了.$QAQ$.

然后还有一个很神的方法是直接贪心,大概港下$QwQ$.

先考虑如果只有一个宿管,显然能合法就尽量合法,设当前合法的房间数为$cnt$,就直接看$\sum_{j=1}^{i+d\cdot i}$和$(cnt+1)\cdot b$的关系就成.正确性十分显然?就对于不合法的房间,反正都不合法了不如直接所有人都逃出去给后面的房间做贡献嘛$QwQ$.

然后现在变成了两个宿管,发现分别这么做就行$QwQ$.

大概证明下两边是麻油影响的,,,,?首先当两边能调配的人不重叠的时候正确性是显然的,要考虑的就只有重叠的时候的重叠那一段.

考虑如果发生影响了,一定是左右两边对中间的人的需求量大于中间人的数量了.但是发现这是不可能的.考虑设左侧不重叠的数量为$x$,右侧不重叠的数量为$y$,左侧需求等于右侧需求等于$d$,然后中间的人数量就是$n\cdot b-x-y$.

现在如果先优先满足左边的需求,也就说剩余的人的数量就是$n\cdot b-d-y$,现在要比较这个数与$d-y$的关系.

因为显然有$n\cdot b\geq 2\cdot d$,所以有$n\cdot b-d-y\geq d-y$,也就说不存在上面猜测的需求量大于数量的情况,所以一定没有影响.

所以分别做着就成$QwQ$.

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define int long long

#define t(i) edge[i].to

#define ri register int

#define rc register char

#define rb register bool

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+;

int n,d,b,sum[N],as1,as2,t;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

signed main()

{

    //freopen("949d.in","r",stdin);freopen("949d.out","w",stdout);

    n=read();d=read();b=read();rp(i,,n)sum[i]=sum[i-]+read();

    rp(i,,n>>){if(sum[min(n,i*(d+))]>=b*(as1+))++as1;if(sum[n]-sum[max(0ll,n-i*(d+))]>=b*(as2+))++as2;}

    if(n&){t=(n+)>>;if(sum[min(n,t*(d+))]>=b*(as1+))++as1;}else t=n>>;

    printf("%lld\n",max(t-as1,(n>>)-as2));

    return ;

}

随机推荐

  1. Flask学习之十二 使用boostrap

    英文博客地址:http://blog.miguelgrinberg.com/post/the-flask-mega-tutorial-part-xii-facelift 中文翻译地址:http://w ...

  2. asp.net抓取网页html源代码失败 只因UserAgent作怪

    asp.net抓取网页html源代码,我想对于任何一个asp.net程序员来说都不再陌生,这是一个非常简单容易就能实现的功能.下面便是一个通用的asp.net获得网页源代码的程序. 首先引用 usin ...

  3. 下载mysql document

    wget -b -r -np -L -p https://dev.mysql.com/doc/refman/5.6/en/ 在下载时.有用到外部域名的图片或连接.如果需要同时下载就要用-H参数. wg ...

  4. Getting started with the basics of programming exercises_3

    1.编写一个程序删除每个输入行末尾的空格及制表符并删除完全是空白符的行 #include<stdio.h> #define MAXLINE 1000 // maximum input li ...

  5. @noi.ac - 492@ casino

    目录 @description@ @solution@ @solution@ @part - 1@ @part - 2@ @part - 3@ @accepted code@ @details@ @d ...

  6. 【原生JS】写最简单的图片轮播

    非常简单的一个大图轮播,通过将控制显示位置来进行轮播效果,写来给正在学习的新手朋友们参考交流. 先看效果:(实际效果没有这么快) 先看布局: <div id="display&quot ...

  7. 洛谷P3377 【模板】左偏树（可并堆） 题解

    作者:zifeiy 标签:左偏树 这篇随笔需要你在之前掌握 堆 和 二叉树 的相关知识点. 堆支持在 \(O(\log n)\) 的时间内进行插入元素.查询最值和删除最值的操作.在这里,如果最值是最小 ...

  8. 2019-7-29-PowerShell-拿到显卡信息

    title author date CreateTime categories PowerShell 拿到显卡信息 lindexi 2019-7-29 10:3:35 +0800 2019-02-21 ...

  9. java构造方法的私有化

    有的时候我们为了避免外界创建某类的实例,就将某类的构造方法私有化,即将它的构造方法用private修饰: 外界如何用到? 提供get方法!不提供的话外界就没法创建对象!(对反射无效) Eg:packa ...

  10. C# GUID ToString

    最近在看到小伙伴直接使用 Guid.ToString ,我告诉他需要使用 Guid.ToString("N") ,为什么需要使用 N ,因为默认的是 D 会出现连字符. Guid ...

相关文章