Codeforces 460C

比较裸的二分,但是比赛的时候脑抽,用树状数组瞎搞过了,但是边界条件没注意让hack了。

后来看到有人写了很简单的版本,又过了一遍,提醒一下自己不能忘记基本算法。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int a[100005],b[100005],sum[100005];
int n,m,k;
bool judge(int mid)
{
    int step=m,add=0;
    memset(sum,0,sizeof(sum));
    for(int i=0;i<n;i++)
    b[i]=a[i];
    for(int i=0;i<n;i++)
    {
        add+=sum[i];
        b[i]+=add;
        if(b[i]<mid)
        {
            int temp=mid-b[i];
            b[i]=mid;
            step-=temp;
            add+=temp;
            sum[min(i+k,n)]-=temp;
            if(step<0)
            return false;
        }
    }
    return true;
}
int main()
{
    while(cin>>n>>m>>k)
    {
        int minn=1e9;
        int maxx=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            minn=min(minn,a[i]);
            maxx=max(maxx,a[i]);
        }
        int low=minn,high=m+maxx;
        int ans=minn;
        while(low<=high)
        {
            int mid=(low+high)>>1;
            if(judge(mid))
            {
                ans=max(ans,mid);
                low=mid+1;
            }
            else
            high=mid-1;
        }
        cout<<ans<<endl;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 95 Unique Binary Search Trees II

    Given an integer n, generate all structurally unique BST's (binary search trees...

    triplebee
  • 水题第二弹题解

    改过的标题很具有迷惑性哦! A POJ3414本次代码量最大的一题,思想是搜索,详细解题报告,请见点击打开链接 B巨水,不要被题目迷惑了,连通图的性质最少需要(...

    triplebee
  • Leetcode 223. Rectangle Area

    Find the total area covered by two rectilinear rectangles in a 2D plane. Each ...

    triplebee
  • 算法-归并排序

    瑞新
  • 论分治与归并思想

    要想了解归并思想,就离不开对归并排序的理解,从前看别人的代码百思不得其解,后来看到一张图片顿时领悟,附下:

    _DIY
  • 深度优先搜索(DFS)

    深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只...

    刘开心_1266679
  • 信息竞赛进阶指南--归并排序求逆序对

    风骨散人Chiam
  • 每天一道leetcode069-x的平方根

    实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。...

    乔戈里
  • Android必知必会 - RecyclerView 恢复上次滚动位置

    记录 RecyclerView 滚动位置并恢复是一个很常见的需求,通常需要精准恢复到上次的位置。

    他叫自己MR.张
  • 【模板小程序】二分法插入排序

    Java版源程序来自:http://www.cnblogs.com/PerkinsZhu/p/5674572.html,在此感谢。

    xiaoxi666

扫码关注云+社区

领取腾讯云代金券