CF949D Curfew（贪心）

原题

挂个链接CodeForces

题目大意：详情参见洛谷CF949D
洛谷这题的翻译还真的不错。

Solution

分析:

很显然的,题目明显告诉我们,要求最大值的最小值,也就是最小化最大值,所以我们考虑二分答案.

但是这题并不需要二分答案,贪心就可以过.

我们考虑如果我们可以满足一个房间那么现在就满足他一定不会让答案变差,这很显然吧…

然后我们考虑如果一边满足了,显然就只需要考虑另一边.

所以只需要对于一边搞,然后贪心的算答案就好了.

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<iostream> #include<queue> #include<algorithm> #define ll long long #define re register using namespace std; inline int gi(){ int sum=0,f=1;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum; } inline ll gl(){ ll sum=0,f=1;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum; } int n; ll a[],s[],d,b; int main(){ n=gi();d=gl();b=gl(); for(re int i=1;i<=n;i++)a[i]=gl(); for(re int i=1;i<=n;i++)s[i]=s[i-1]+a[i]; int cnt1=0,cnt2=0; for(re int i=1;i<=n/2;i++){ ll x=s[min(1ll*n,i*(d+1))]-1ll*cnt1*b; if(x>=b)cnt1++; x=s[n]-s[max(0ll,n-i*(d+1))]-1ll*cnt2*b; if(x>=b)cnt2++; } printf("%d\n",n/2-min(cnt1,cnt2)); return 0; }