头像

浅语




在线 



浅语
9天前

题目描述

在一条数轴上有 N 家商店,它们的坐标分别为 A1~AN。

现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。

为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

输入格式
第一行输入整数N。

第二行N个整数A1~AN。

输出格式
输出一个整数,表示距离之和的最小值。

数据范围
1≤N≤100000,
0≤Ai≤40000

样例

输入

4
6 2 9 1

输出

12

方法一(排序)

只需要简单的快排取中位数即可。

时间复杂度

O(nlogn),其中n为数组大小

C++ 代码

#include<bits/stdc++.h>
using namespace std;
//方法①
//采用快排的方式确定中位数,时间复杂度为O(nlogn);
int main(){
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int num[n];
    for(int i=0;i<n;i++)cin>>num[i];
    sort(num,num+n);
    int k=(0+n-1)/2;
    long long sum=0;
    for(int i=0;i<n;i++){
        sum+=abs(num[i]-num[k]);
    }
    cout<<sum<<endl;
    return 0;
}

方法二 (二分)

该方法是通过二分来找到解,思想就是我们在可能的解空间内二分,在每个二分的值下验证是不是恰好有(n+1)/2个元素是大于等于该值的,如果是,则该值就是货仓应该建立的位置,否则继续二分,直到搜索到的解满足条件为止。

时间复杂度

时间复杂度是O(nlogC)的,其中C是指数组元素中的极差大小。

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int num[n];
    for(int i=0;i<n;i++)cin>>num[i];
    int l=0;
    int r=100000;
    for(;l<=r;){
        int m=(l+r)/2;
        int count=0;
        for(int i=0;i<n;i++)if(num[i]-m>=0)count++;
        if(count<(n+1)/2)r=m-1;
        else l=m+1;
    }
    long long ans=0;
    for(int i=0;i<n;i++)ans+=abs(num[i]-l+1);
    cout<<ans<<endl;
    return 0;
}



浅语
1个月前

动态规划(ST算法)

本题是非常明显的RMQ问题,如果了解过这方面的知识,可以很自然的想到ST算法;ST算法是动态规划算法,通过O(nlogn)的预处理时间,可以实现O(1)时间内的查询,算法的依据我认为更像是通过选定一定的区间长度,作为编码,而快速合成其他区间的过程。具体我这里就不描述了,大家可以自行上网学习ST算法,这里只给出我的解决方案。

代码

//单调队列和RMQ
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int num[n+1];
    for(int i=1;i<n+1;i++)cin>>num[i];
    int k=log2(n)+1;
    int dp[n+1][k];
    int tp[n+1][k];
    for(int i=0;i<k;i++){
        for(int j=1;j<=n;j++){
            dp[j][i]=INT_MAX;
            tp[j][i]=INT_MIN;
        }
    }
    for(int i=1;i<n+1;i++){
        dp[i][0]=num[i];
        tp[i][0]=num[i];
    }
    for(int i=1;(1<<i)<n;i++){//循环顺序要合理,一定要注意已经初始化了,dp只需要求解长度为2的即可. 
        for(int j=1;j+(1<<i)-1<=n;j++){//区间不要超出边界 
            dp[j][i]=max(dp[j][i-1],dp[j+(1<<i-1)][i-1]);
            tp[j][i]=min(tp[j][i-1],tp[j+(1<<i-1)][i-1]);
        }
    }
    int d=log2(m);
    for(int i=1;i+m-1<=n;i++){
        cout<<max(dp[i][d],dp[i+m-(1<<d)][d])<<" ";
        cout<<min(tp[i][d],tp[i+m-(1<<d)][d])<<endl;
    }
    return 0;
}

时间复杂度显然是O(m+nlogn)的,其中m是查询次数,而n是数据个数。

线段树

类似于ST算法,线段树也是通过一定的空间开销和预处理时间在O(n)的时间复杂度内预处理数据,然后在O(logn)的时间复杂度内查询一个区间,该题也很容易利用线段树的模板进行解决,这里也不详细介绍线段树时什么了。

代码

//单调队列和RMQ
#include<bits/stdc++.h>
using namespace std;

int num[100010];
int dp[400001];
int tp[400001];
int lazy[400001];
void up(int rt){
    dp[rt]=max(dp[rt<<1],dp[rt<<1|1]);
    tp[rt]=min(tp[rt<<1],tp[rt<<1|1]);
    return;
} 
void build(int l,int r,int rt){
    if(l==r){
        dp[rt]=num[l];
        tp[rt]=num[l];
        return;
    }
    int m=(l+r)/2;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    up(rt);
    return ;
}
void down(int rt,int ln,int rn){
    //注意lazy存的是当前节点的子区间应该更新的总值,当前层已经被上层down更新结束,所以无需更新
    //下推时,我们只需要计算下层左右孩子应该更新的值,以及下层左右孩子的lazy值,并将当前层的lazy值设置为1 
    if(lazy[rt]){
        dp[rt<<1]+=lazy[rt]*ln;
        dp[rt<<1|1]+=lazy[rt]*rn;
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        lazy[rt]=0; 
    }
    return ;
}
int querymax(int x,int y,int l,int r,int rt){
    if(x<=l&&y>=r)return dp[rt];
    int m=(l+r)/2;
    down(rt,m-l+1,r-m);
    int ans=INT_MIN;
    if(x<=m)ans=max(ans,querymax(x,y,l,m,rt<<1));
    if(y>m)ans=max(ans,querymax(x,y,m+1,r,rt<<1|1));
    return ans;
}
int querymin(int x,int y,int l,int r,int rt){
    if(x<=l&&y>=r)return tp[rt];
    int m=(l+r)/2;
    int ans=INT_MAX;
    if(x<=m)ans=min(ans,querymin(x,y,l,m,rt<<1));
    if(y>m)ans=min(ans,querymin(x,y,m+1,r,rt<<1|1));
    return ans;
}
int main(){
    int n,m;
    cin>>n>>m;
    memset(num,0,sizeof(num));
    memset(lazy,0,sizeof(lazy));
    for(int i=1;i<=n;i++)cin>>num[i];
    build(1,n,1);//一定要注意的是线段树的根节点序号是1,这是为了便于进位计算,否则需要用到乘法。
    //查询时我们仍然用的是源区间,并且每一次查询都要在整个[1,n]区间上查询,所以下面的表示方法正确。 
    for(int i=1;i+m-1<=n;i++){
        cout<<querymax(i,i+m-1,1,n,1)<<" ";
        cout<<querymin(i,i+m-1,1,n,1)<<endl;
    } 
    return 0; 
}

时间复杂度是O(mlogn+n)的,可以看出当m与n的数量级接近时,线段树与ST算法的时间复杂度是一致的,但是当查询的区间数角度时,线段树的时间复杂度要略高于ST算法。
ST算法只能处理离线的多区间查询,而线段树则可以实现动态区间查询,不过线段树的代码实现更繁琐,所以两者有不同的适应区间。


单调队列

本题的特殊解法,由于要查询的区间是一个滑动窗口,所以很自然我们可以想到用单调队列来解决该问题,下面给出代码实现;

//单调队列和RMQ
#include<bits/stdc++.h>
using namespace std;
int main(){
    //单调队列实现
    int n,k;
    cin>>n>>k;
    deque<int> high;
    deque<int> low;
    int num[n]; 
    for(int i=0;i<n;i++){
        cin>>num[i];
        //注意单调队列的技巧,通常是尾巴保存最大值,并在每次删除不满足条件的最大值 
        for(;!high.empty()&&high.back()<i-k+1;high.pop_back());
        //新添加的值从头部加入,因为考虑的最大值,所以比当前值小的不可能是最大值,所以可以直接删掉 
        for(;!high.empty()&&num[high.front()]<=num[i];high.pop_front());
        high.push_front(i);
        if(i>=k-1)cout<<num[high.back()]<<" ";
        //同理获得较小值的单调队列 
        for(;!low.empty()&&low.back()<i-k+1;low.pop_back());
        for(;!low.empty()&&num[low.front()]>=num[i];low.pop_front());
        low.push_front(i);
        if(i>=k-1)cout<<num[low.back()]<<endl; 
    } 
    return 0;

}

时间复杂度是O(n)的,但是由于需要角度的进队列出队列,判空等操作,实际上常数项并不小,与上面两种方法时间实际运行时间接近。