2118: 签到题 时间限制: 1 Sec 内存限制: 128 MB 提交: 54 解决: 22 [提交] [状态] [讨论版] [命题人:admin] 题目描述
作为acm集训队一员的你，有一天拿到了你的历史训练时长记录表。你当然是想让你的训练时长看起来好看一些，所以你想调整这份记录表，使得训练时长最少的一天的时间在所有可能的调整方案中最大。你还有m分钟就梦醒了，时间紧迫，你每一分钟可以使得连续的w天时长记录多一个单位时间。注意，在梦中，你不需要考虑一天有多少的时间限制。 输出经过你的调整，最小的时长。(睡醒前的答案)
输入
多组数据，第一行为一个整数T，表示数据组数（T<=10) 接下来每组数据，开头为n，m，w（1<=w , n<=100000, 0<=m <= 1000000),表示有记录的历史训练天数 接下来一行n个数，表示这一天你的签到时长t（0<=t<=1000000）
输出
输出T行，每行代表一组的答案。
样例输入
1 3 2 1 2 1 2
样例输出
2
二分答案，差分检查。
#include<bits/stdc++.h> #define fi first #define se second #define log2(a) log(n)/log(2) #define show(a) cout<<a<<endl; #define show2(a,b) cout<<a<<" "<<b<<endl; #define show3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl; #define tim printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); using namespace std; typedef long long ll; typedef pair<ll, ll> P; typedef pair<P, ll> LP; const ll inf = 0x3f3f3f3f; const int N = 2e5+10; const ll mod = 1e12; const ll p=1e6; const int base=131; const double pi=acos(-1); int a[N],n,rm,w,m; int num[N]; bool check(int x) { for(int i=1;i<=n;i++) num[i]=0; int t; m=rm; for(int i=1;i<=n;i++) { num[i]+=num[i-1]; if(num[i]+a[i]<x) { t=x-a[i]-num[i]; m-=t; num[i]+=t; num[i+w]-=t; } } return m>=0 ? 1 : 0; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&rm,&w); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int l=0,r=2000001,ans; while(l<=r) { int mid=l+r>>1; if(check(mid)) { ans=mid; l=mid+1; } else r=mid-1; } printf("%d\n",ans); } }