Codeforces 460C Present 二分答案

题目链接：http://codeforces.com/contest/460/problem/C

题意： 

给定一个n长的序列

每次可以给w长的区间内的数增加1

最多可以增加m次

使得 最后结果中最小的数 最大

问这个最小的数是多少

二分答案判可行。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define inf 1000000000
#define N 100005
int a[N];
int b[N], add[N];
bool ok(int x, int n, int m, int w){
for(int i = 1; i<= n; i++)b[i] = a[i];
memset(add, 0, sizeof add);
int now = 0;
for(int i = 1; i <= n; i++){
now += add[i];
b[i] += now;
if(b[i]<x){
int go = x - b[i];
b[i] += go;
m -= go;
now += go;
add[min(N-1,i+w)] -= go;
if(m<0)return false;
}
}
for(int i = n; i ; i--)
if(b[i]<x)return false;
return true;
}
int n, w, m;
int main() {
while(~scanf("%d %d %d",&n,&m,&w)){
int minn = inf, maxx = 0;
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
minn = min(minn, a[i]);
maxx = max(maxx, a[i]);
}
int ans = minn;
int l = minn, r = maxx + m;
while(l <= r){
int mid = (l+r)>>1;
if(ok(mid, n, m, w))
ans = max(ans, mid), l = mid+1;
else
r = mid-1;
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是鲜艳书本为你收集整理的Codeforces 460C Present 二分答案的全部内容，希望文章能够帮你解决Codeforces 460C Present 二分答案所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。