差分,二分_吐泡泡的咸鱼的博客-程序员宅基地

技术标签: 差分  

题目链接:传送门

题意:
给你n个数,以及修改的区间长度,每次修改区间中的加1,求最后所有数相同,最少的操作数。
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,K;
ll A[maxn],sumA[maxn],addA[maxn];
ll check(ll upper){
    
    int i;
    ll sum,tmp,ret;
    addA[n+1]=0;sum=tmp=ret=0;
    for (i=1;i<=n;i++)addA[i]=0;
    for (i=1;i<=n;i++){
    
        sum+=addA[i];
        if(A[i]+sum>upper)return -1;
        else if(A[i]+sum==upper)continue;
        else{
    
            if(i+K-1>n)return -1;
            tmp=upper-(A[i]+sum);
            ret+=tmp;addA[i]+=tmp;addA[i+K]-=tmp;sum+=tmp;
        }
    }
    return ret;
}
int main(){
    
    int i,k,tCase;
    ll maxx,x,l,r,mid,ret,ans;
    scanf("%d",&tCase);
    while(tCase--){
    
        scanf("%d%d",&n,&K);maxx=0;
        for (i=1;i<=K;i++)sumA[i]=0;
        for (i=1;i<=n;i++){
    
           scanf("%lld",&A[i]),maxx=max(maxx,A[i]);
           k=i%K;
           if(k==0)k=K;
           sumA[k]+=A[i];
        }
        if(n%K!=0){
    
          k=n%K;k++;
          x=sumA[1]-sumA[k];
          if(x<maxx)printf("-1\n");
          else printf("%lld\n",check(x));
        }
        else{
    
          for(i=2;i<=K;i++)if(sumA[1]!=sumA[i])break;
          if(i<=K){
    
             printf("-1\n");continue;
          }
          l=maxx,r=1e10;ans=1e16;
          while(l<r){
    
             mid=(l+r)>>1;
             ret=check(mid);
             if(ret!=-1)ans=min(ans,ret),r=mid-1;
             else l=mid+1;
          }
          if(r>=maxx){
    
            ret=check(r);
            if(ret!=-1)ans=min(ans,ret);
          }
          if(l>=maxx){
    
            ret=check(l);
            if(ret!=-1)ans=min(ans,ret);
          }
          if(ans==1e16)printf("-1\n");
          else printf("%lld\n",ans);
        }
    }
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39507939/article/details/114145905

智能推荐

软件研发公司的招聘实习生的工资会有6000~8000这么高?是骗人的吗?_实训001的博客-程序员宅基地

聊到实习生,大家会想到什么呢?大厂螺丝钉?免费劳动力?打印复印?跑腿?端茶倒水?实习生不是来端茶倒水的,而且从我个人来看,相比老员工,优秀的实习生能给项目带来改变显然更多。换位思考一下:你的组突然来了一个比你年轻、比你听话、比你努力、比你有活力、比你学得快的,你有没有危机感?我可能更愿意招一个性价比极高、听话勤奋的毕业生,而不是一个工作了四五年虽然能力不错但沾染了各种职业恶习的社招人员。不过这个都因人而异了,不同的行业不同的公司不同的项目有着各种丰富多彩的现实和事实,我只是想说:IT互联网这个行

megacli 查看Raid卡和硬盘信息_weixin_33682790的博客-程序员宅基地

megacli的安装通过如下链接http://down.51cto.com/data/2042596或者http://pan.baidu.com/s/1eQ2FeHc下载至windows本地桌面,然后在linux命令行用命令:rz -be ,在弹出的窗口中选择刚才下载的压缩包(注意不要勾选已ASCII码方式传送文件)tar xf megacli-8.02.21-1-mdv20...

Vue 路由 详细总结_YuLong~W的博客-程序员宅基地_vue路由总结

文章目录路由基本使用多级路由命名路由路由的参数query参数params参数路由其它props配置replace属性编程式路由导航缓存路由组件两个新的生命周期钩子路由守卫路由器的两种工作模式路由一个路由(route)就是一组 映射关系(key - value),多个路由需要 路由器(router) 进行管理。前端路由:key是路径,value是组件基本使用安装vue-router,命令:npm i vue-router应用插件:Vue.use(VueRouter)编写router配

GNSS连续运行单参考站解决方案_七星耀华的博客-程序员宅基地

一、前言随着国家信息化程度的提高及计算机网络和通信技术的飞速发展,电子政务、电子商务、数字城市、数字省区和数字地球的工程化和现实化,需要采集多种实时地理空间数据,因此,中国发展CORS系统的紧迫性和必要性越来越突出。几年来,国内不同行业已经陆续建立了一些专业性的卫星定位连续运行网络,目前,为满足国民经济建设信息化的需要,一大批城市、省区和行业正在筹划建立类似的连续运行网络系统,一个新的建网高潮正在到来。当前国内不同行业建设的网站系统基本上还是独立运行的,很多单位的数据只在本单位甚至是本部门内共享和利

android定义多个上下文菜单,Android编程实现为ListView创建上下文菜单(ContextMenu)的方法..._燕尾蝶田的博客-程序员宅基地

本文实例讲述了Android编程实现为ListView创建上下文菜单(ContextMenu)的方法。分享给大家供大家参考,具体如下:ContextMenu称为上下文菜单,一般在控件上长按时弹出。今天我们学习ContextMenu的用法,这里与listview相结合,先在ListView显示几个Item,然后在Item上长按,弹出一个菜单(就是ContextMenu),点击菜单上的项目,提示刚才长...

eval 方法_luxuejuncarl的博客-程序员宅基地

 eval 方法检查 JScript 代码并执行. eval(codeString)必选项 codestring 参数是包含有效 JScript 代码的字符串值。这个字符串将由 JScript 分析器进行分析和执行。说明eval 函数允许 JScript 源代码的动态执行。例如,下面的代码创建了一个包含 Date 对象的新变量 mydate :eval("var myd

随便推点

一个细节问题:无法将类 com.tour.info.admin.service.TempService中的方法 indexZtemp应用到给定类型;_是这耀眼的瞬间的博客-程序员宅基地_无法将接口中方法应用到给定类型

Error:(88, 25) java: 无法将类 com.tour.info.admin.service.TempService中的方法 indexZtemp应用到给定类型;  需要: java.lang.Integer,javax.servlet.http.HttpServletRequest  找到: javax.servlet.http.HttpServletRequest,jav

为什么曾经优秀的人突然变得平庸?_互联网全栈架构的博客-程序员宅基地

一个读者的提问:洋哥,我从小都是学霸,本硕都是985,计算机科班出身,但进入职场后却始终无法取得突破。工作5年还是基层员工,我该怎么破局?这个问题让我陷入了沉思,身边不不少曾经很厉害的朋友...

mybatis常用jdbcType数据类型_夕暮丶迟的博客-程序员宅基地

MyBatis 通过包含的jdbcType类型BIT         FLOAT      CHAR           TIMESTAMP       OTHER       UNDEFINEDTINYINT     REAL       VARCHAR        BINARY          BLOB        NVARCHARSMALLINT    DOUBLE

吴恩达机器学习编程题四(神经网络-BP)(python)_Sep4_J的博客-程序员宅基地

import numpy as npimport scipy.io as sioimport matplotlib.pyplot as pltfrom scipy.optimize import minimizedata = sio.loadmat('ex4data1.mat')raw_X = data['X']raw_y = data['y']X=np.insert(raw_X,0,values=1,axis=1)X.shapedef one_hot_encoder(raw_y):

自定义触发器报警_weixin_46837396的博客-程序员宅基地

一、自定义触发器报警点击配置—点击主机—点击触发器===点击创建你触发器触发器的名称以及表达式{主机名:key;last()}{主机名:\key:avg(5m)}{主机名:\key:nodata(5m)}自定义触发器表达式进阶二、邮件报警和微信报警邮件报警1.定义发件人...

Oracle 集合转字符,PL/SQL Challenge 每日一题:2014-5-30 将逗号隔开的字符串转换为集合..._App Growing的博客-程序员宅基地

最先答对且答案未经编辑的puber将获得纪念章一枚(答案不可编辑但可发新贴补充或纠正),其他会员如果提供有价值的分析、讨论也可获得纪念章一枚。以往旧题索引:http://www.itpub.net/forum.php?m ... eid&amp;typeid=1808原始出处:http://www.plsqlchallenge.com/作者:Steven Feuerstein运行环境:SQLPLU...