CF949D Curfew

传送门

跟这个大佬学的->戳我

假设只有一个宿管,那么从前往后做的过程中,如果能到达某个寝室范围内的人数不够\(b\),那么不如把这个寝室空出来,这样更有利于后面的抉择;反之,就把这个寝室搞正好\(b\)个人,在前面搞好一个寝室是要比在后面搞好有利的,这样就可以记个前缀和,然后一路贪心

现在有两个宿管,假设先只考虑一半,满足一半后剩下的人就可以去满足另一半,而且不会使另一半的空寝室增加1以上(吧)

然后两边分别贪心救星

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define db double

#define eps (1e-5)

using namespace std;

const int N=100000+10;

il LL rd()

{

    re LL x=0,w=1;re char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int n,d,b,ans,a1,a2;

int s1[N],s2[N];

int main()

{

  n=rd(),d=rd(),b=rd();

  for(int i=1;i<=n;i++) s1[i]=s2[n-i+1]=rd();

  for(int i=1;i<=n;i++) s1[i]+=s1[i-1],s2[i]+=s2[i-1];

  for(int i=1,res=0;i<=(n+1)/2;i++)

    {

      if(s1[min(1ll*i*(d+1),1ll*n)]-s1[i-1]+res>=b) res-=b,++a1;

      res+=s1[i]-s1[i-1];

    }

  for(int i=1,res=0;i<=n/2;i++)

    {

      if(s2[min(1ll*i*(d+1),1ll*n)]-s2[i-1]+res>=b) res-=b,++a2;

      res+=s2[i]-s2[i-1];

    }

  printf("%d\n",max((n+1)/2-a1,n/2-a2));

  return 0;

}