$CF949D Curfew$ 二分/贪心

正解:二分/贪心

解题报告:

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

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

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

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

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

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

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

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

因为显然有$ncdot bgeq 2cdot d$,所以有$ncdot b-d-ygeq 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=1000000+10;
int n,d,b,sum[N],as1,as2,t;

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),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,1,n)sum[i]=sum[i-1]+read();
    rp(i,1,n>>1){if(sum[min(n,i*(d+1))]>=b*(as1+1))++as1;if(sum[n]-sum[max(0ll,n-i*(d+1))]>=b*(as2+1))++as2;}
    if(n&1){t=(n+1)>>1;if(sum[min(n,t*(d+1))]>=b*(as1+1))++as1;}else t=n>>1;
    printf("%lld
",max(t-as1,(n>>1)-as2));
    return 0;
}

View Code