博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
AtCoder Regular Contest 100 C:Linear Approximation解题报告
阅读量:7175 次
发布时间:2019-06-29

本文共 631 字,大约阅读时间需要 2 分钟。

题目大意:这次比赛所有的题目都描述的很简单,我这种英语不好的也能一看就懂。给你N个数存为Ai,请你给出一个b,使abs(A1−(b+1))+abs(A2−(b+2))+…+abs(AN−(b+N))最小,输出这个最小值。

思路:一看到绝对值,就应该想到数轴上点之间的距离,这道题虽然给b加上了i,但只要把式子拆开,一开始就把每个Ai减去i就行了。然后可以证明(或者学过)一个点到其他点距离和最短应该是这些点坐标集合的中位数,然后直接写就行了。(一定要记得用long long!)

AC程序

//库省略const int maxn=200005;ll n,d,k;ll a[maxn];int main(){    cin>>n;    for(int i=1;i<=n;i++)    {        cin>>a[i];        a[i]-=i;    }    sort(a+1,a+n+1);    ll b=0;    if(n%2==0)    b=(a[n/2]+a[n/2+1])/2;    else    b=a[n/2+1];    ll ans=0;    for(int i=1;i<=n;i++)    {        ans=ans+abs(b-a[i]);    }    cout<
<

转载于:https://www.cnblogs.com/NightRaven/p/9333246.html

你可能感兴趣的文章
nodejs终端的坑--新手向
查看>>
pycharm修改默认__author__ = '$USER'
查看>>
DNS服务的原理与配置(详细图文教程)
查看>>
threejs 之box贴图--6个 面集中在一个图片上
查看>>
Exchange Server 2010安装测试
查看>>
设计模式第九课 策略模式
查看>>
给定两个排序后的数组A和B,其中A的末端有足够的缓冲空间容纳B。将B合并入A并排序...
查看>>
FFmpeg avcodec_version函数使用
查看>>
一步步手动构建小于10M的类嵌入式Linux系统
查看>>
saltstack细节要点
查看>>
端口回流与dns-map与域内NAT
查看>>
linux 中特殊符号用法详解
查看>>
转载自马哥视频学习笔记---awk的基本用法说明
查看>>
Unity3D加密流程文档
查看>>
Java多线程同步的五种方法
查看>>
ConcurrentHashMap、synchronized与线程安全
查看>>
点击两次返回键退出程序(简洁)
查看>>
(九)企业部分之Varnish
查看>>
在sublime中,css设置snippet后缀源要写.less才生效(内附50个css代码段链接)
查看>>
2015.05.26 工作任务与心得
查看>>