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

技术标签：差分

题目链接：传送门

题意：
给你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;
}

本文链接：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