首页 > 其他分享 >货仓选址(贪心)(也可以二分)(还可以三分)

货仓选址(贪心)(也可以二分)(还可以三分)

时间:2022-09-27 21:00:39浏览次数:76  
标签:二分 货仓 int 位置 long maxn include 贪心

货仓选址(贪心)

题目大意:给你N个位置(在同一条轴上的),求出在这些位置中的一个位置,使得所有位置到这个位置的和最小

利用贪心思想,如果选取的位置不在中心,那么向左或者向右移动的距离之和的增量是不同的,有正数有负数,只有当选取的位置在中心的时候才会让选取的位置不管向左还是向右移动增量都为正数,所以中间是最好的位
////这道题目其实二分也可以写,只要控制好精度问题,在输出的时候输出整数部分;

AC代码(版本一)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=100010;
int num[maxn];
int main(void)
{
    int N;scanf("%d",&N);
    for(int i=0;i<N;i++)scanf("%d",&num[i]);
    sort(num,num+N);
    ll ans=0;
    for(int i=0;i<N;i++)
        ans+=abs(num[i]-num[N>>1]);
    cout<<ans<<endl;
    return 0;
}

(版本二)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=100010;
int num[maxn];
int main(void)
{
    int N;scanf("%d",&N);
    for(int i=0;i<N;i++)scanf("%d",&num[i]);
    sort(num,num+N);
    ll ans=0;
    for(int i=0;i<N;i++)
        ans+=num[i]-num[i>>1];//不断的改变中间的位置,每次的改变都只会增加新的点到中间位置的距离
    cout<<ans<<endl;
    return 0;
}

标签:二分,货仓,int,位置,long,maxn,include,贪心
From: https://www.cnblogs.com/WUTONGHUA02/p/16735963.html

相关文章

  • java 封装一个二分查询函数
    packageBinarySearch;importjava.lang.reflect.Array;publicclassTest{publicstaticvoidmain(String[]args){intarr[]={2,6,7,8,9,11,13,......
  • CDQ&整体二分-三维偏序(陌上花开)
    题面本文讲cdq,整体二分的思路与做法。=分治VS数据结构其实维度这一方面,空间几何可以是维度,像时间这样有规定顺序的词语也可能是维度。cdq三维偏序,一般可以用一维一维的......
  • 贪心杂题
    \(Preface\)最近咋老考贪心嘞?我的数据结构呢?贪心这玩意确实重要。但是我蒟蒻,老做不出来,而且经常写挂某些需要用到一些小技巧的题。。。具体地,刷贪心题既是刷思维也是刷......
  • Fenwick 树状数组上二分
    其实应该叫倍增。由于这篇文章中\(\text{lowbit}\)Acwing244.谜一样的牛给定一个长度\(n\le10^5\)序列,求逆康托。\(0\lea_i<i\)若是\(\logn\)二分,再\(\lo......
  • mex(权值线段树+线段树上二分)
      思路:首先看到区间维护,想到线段树,但是很明显无法用线段树直接维护区间最小没出现过的自然数,因为假若一个节点的左右儿子节点的值都为0,我们是无法推断出父节点的值是几......
  • 二分查找算法
    简介只能对有序数组进行查找代码实现publicclassBinarySearch{ publicstaticvoidmain(String[]args){ //查找单个数据 intarr[]={1,8,10,8......
  • 二分查找模板
    //arr数组升序//n是数组长度,也就是lr正好是数组的左右的第一个和最后一个intl=0,r=n-1;intmid;while(l<=r){mid=(l+r)/2;if(arr[mid]==......
  • 二分查找步骤及问题总结
    二分查找参数:有序数组arr(这里按升序来讲),待搜索的值target步骤定义左边界left和有边界right获取中间索引(整数)mid=(left+right)/2,注意:js只有小数,mid需要再取整......
  • 二分模板
    intsearch(vector<int>&nums,inttarget){intleft=0,right=nums.size();intmid;while(left<right){mid=(left+right)>>1;......
  • 实例84 二分法求解方程
    #include<stdio.h>#include<math.h>#include<malloc.h>#include<stdlib.h>doubleFunc(double);intBisectRoot(double,double,double,double,double*,int,in......