首页 > 其他分享 >3224. 使差值相等的最少数组改动次数

3224. 使差值相等的最少数组改动次数

时间:2024-08-09 15:49:42浏览次数:13  
标签:改动 操作数 int 3224 差值 数组 题解 区间 max

原题链接

前情提要,结合原题解区的题解

题解

先简化问题,对于一对数 \(a,b\),其中 \(a\leq b\),要使其差为 \(X\) 的操作数是多少?

分类讨论

1.如果 \(b-a==X\),操作数为 \(0\)(不操作)

2.如果 \(X\lt b-a\),操作数为 \(1\)(增加a或者减小b)

3.如果 \(X \in [b-a+1,k-a]\),操作数为 \(1\)(增大b)

4.如果 \(X\in [b-a+1,b]\),操作数为 \(1\)(减小a)

5.否则操作数为 \(2\)(增加b,同时减小a)

实现

对于 \(X\in[0,b-a)\cup [b-a+1,\max(k-a,b)]\) 的区间操作数为 1

对于 \(X\in[b-a,b-a]\) 的区间,操作数为 \(0\)

对于 \(X\in(\max(k-a,b),k]\) 的区间,操作数为 \(2\)

相当于区间修改,单点查询(一次),因此可以用差分数组解决

code

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> d(k+3,0);
        for(int i=0;2*i<n;i++)
        {
            int a=min(nums[i],nums[n-i-1]);
            int b=max(nums[i],nums[n-i-1]);
            int m1=b-a;
            int m2=max(k-a,b);
            d[0]++;
            d[m1]--;

            d[m1+1]++;
            d[m2+1]--;

            d[m2+1]+=2;
            d[k+1]-=2;
        }

        int ans=d[0];
        for(int i=1;i<=k;i++) 
        {
            d[i]+=d[i-1];
            ans=min(ans,d[i]);
        }
        return ans;
    }
};

标签:改动,操作数,int,3224,差值,数组,题解,区间,max
From: https://www.cnblogs.com/pure4knowledge/p/18350861

相关文章

  • 二分查找 | 绝对差值和
    题目:1818.绝对差值和给你两个正整数数组nums1和nums2,数组的长度都是n。数组nums1和nums2的绝对差值和定义为所有|nums1[i]-nums2[i]|(0<=i<n)的总和(下标从0开始)。你可以选用nums1中的任意一个元素来替换nums1中的至多一个元素,以最小化绝......
  • 绝对差值减去百分比
    我有一个DataFrame来查找python中两个源之间的绝对差异百分比。但是当我使用下面的代码时,很少有列给出-%(负百分比)我已经检查了显示负百分比数据类型的列在两个源中是否相同。任何人都可以帮助我找出答案为什么?#Definethecolumnsyouwanttoprocesscolum......
  • [lnsyoj300/luoguP3224/HNOI2012]永无乡
    题意给定\(n\)个集合,每个集合最开始只包含数\(a_i\),然后进行\(m\)次合并操作。具体地,每次操作将数\(a_i\)所在的集合与数\(a_j\)所在的集合合并。接下来,进行\(q\)次操作,每次操作可能为合并操作与查询操作,合并操作与上述相同,查询操作为查询数\(a_x\)所在的集合中第......
  • 游戏陪玩系统源码,时间转换及时分秒差值计算
    游戏陪玩系统源码,时间转换及时分秒差值计算时间转换(秒数转时分秒)functiontimeFormat(sec){letminite=Math.floor((sec/60%60))<10?'0'+Math.floor((sec/60%60)):Math.floor((sec/60%60));letsecond=Math.floor((sec%60))<10?......
  • 海豚调度监控:新增依赖缺失巡检,上游改动再也不用担心了!
    ......
  • dotnet 6 破坏性改动 仅引用程序集输出路径变更
    在dotnet5开始,可以设置ProduceReferenceAssembly为true让项目构建时输出仅引用程序集。仅引用程序集是仅导出项目的公开成员定义,而不包含具体的实现的代码逻辑。只用来被其他项目引用,体积很小,但不用来作为最终发布文件在此前的如下博客里面已经告诉大家如何创建仅引用程序......
  • 【Azure Event Hub】原生应用中使用RabbitMQ,是否可以不改动代码的情况下直接转换为使
    问题描述原生应用中使用RabbitMQ,是否可以不改动代码的情况下直接转换为使用AzureEventHub呢? 问题解答RabbitMQ使用的协议是AMQP0-9-1,而AzureEventHub或ServiceBus使用的是AMQP1.0,所以无法直接复用之前的代码。需要使用AzureEventHubSDK来生产/消费消息。Which......
  • 阅读者如何验证收到的PDF文档的真实性和完整性,判断是否为原作者所发布或是否已被在改
    阅读者如何验证收到的PDF文档的真实性和完整性,判断是否为原作者所发布或是否已被在改动?只有用数字证书签名,这是一种确保文档完整性和验证作者身份的有效方式。如果原作者在发布PDF前对其进行了数字签名,任何后续的修改都会导致签名失效,阅读者在打开文件时会收到警告,提示文件已被......
  • GIS之arcgis系列09:arcpy实现克里金差值
    矢量点数据经过克里金差值后可以转换成栅格数据,那么就需要了解一下什么是克里金差值。什么是克里金法?IDW(反距离加权法)和样条函数法插值工具被称为确定性插值方法,因为这些方法直接基于周围的测量值或确定生成表面的平滑度的指定数学公式。第二类插值方法由地统计方法(......
  • DreamJudge-1290-日期差值
    1.题目介绍题目描述TimeLimit:1000msMemoryLimit:256mb有两个日期,求两个日期之间的天数,如果两个日期是连续的我们规定他们之间的天数为两天输入输出格式输入描述:有多组数据,每组数据有两行,分别表示两个日期,形式为YYYYMMDD输出描述:每组数据输出一行,即日期差值输......