97 条题解

  • 11
    @ 2017-04-06 13:01:21

    1. 首先,输入数据的第一个数是没用的。
    2. 其次,对于第二个数排序。
    3. 取出中位数。
    4. 计算结果。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main() {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp >> a[i];
        }
        sort(a, a + n);
        int pos = a[n / 2], result = 0;
        for (int i = 0; i < n; i++)
            result += abs(a[i] - pos);
        cout << result << endl;
        return 0;
    }
    
    • @ 2019-09-15 16:56:42

      关于中位数部分:在n为偶数时,中位数为中间两个数的平均数((a[n/2]+a[n/2-1])/2);在n为奇数时,中位数为其中间数(a[n/2]).

  • 2
    @ 2018-07-18 20:58:25

    此题为数组的中位数,有几种思路:
    (1)最容易想到的当然是使用数组排序,然后最中间的数(或者中间两个的平均值)即为中位数,因为不需要稳定采用快排,时间复杂度为O(nlogn)+O(1);

    (2)第二种也很容易想到,我们只需要求中间的位数,那么即转换为求第n/2个数(对于偶数的数组则求两个),那么我们不必对整个数组进行排序,利用第K最小值的算法即可求出,时间复杂度2 * O(n);

    注:思路在求偶数数组中位数的时候是两个数的平均值,其实依照题意对于偶数数组我们只需取两个的任意一个即可,所以实际上(2)的时间复杂度可以减少为O(n)。

    (3)第三种是利用Y值是整数,并且范围为-10000≤x,y≤10000,那我们可以利用桶排序,然后再依次累加则到中位数为止,采用空间换时间的方法来减少计算的代价,最差时间复杂度为O(n),平均时间复杂度为O(n/2)。

    本代码采用了第三种桶排序的方法

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    
    using namespace std;
    
    int bucket[20003];
    
    int main()
    {
        //freopen("input.txt", "r", stdin);
        
        int i, j, k;
        int n;
        int x, y;
        //while(scanf("%d", &n) != EOF)
        //{
        scanf("%d", &n);
            memset(bucket, 0, sizeof(bucket));
            for(i = 0; i < n; ++i)
            {
                scanf("%d%d", &x, &y);
                bucket[y + 10000]++;
            }
            
            //求中位数
            int idx1 = (n - 1) / 2;
            int idx2 = n / 2;
            int y1, y2;
            int count = 0;
            for(i = 0; i < 20003; ++i)
            {
                count += bucket[i];
                if(count > idx1) y1 = i;
                if(count > idx2)
                {
                    y2 = i;
                    break;
                }
            }
            y = (y1 + y2) / 2; //两个数中间的任意数值均可,因此无需求实数的平均数
            
            //求最小距离
            int sum = 0;
            for(i = 0; i < 20003; ++i)
            {
                sum += abs(y - i) * bucket[i];  
            } 
            printf("%d\n", sum);
        //}
        
        //fclose(stdin);
        
        return 0;
    }
    
  • 2
    @ 2016-07-22 10:36:54

    注意!暴力可以过

    
    #include<bits/stdc++.h>
    int main()
    {
        int x[10001],y[10001],n;
        scanf("%d",&n);
        long long ans=99999990;
        for(int i=1;i<=n;i++)
          scanf("%d%d",&x[i],&y[i]);
        for(int i=-2500;i<=2500;i++){
            long long sum=0;
            for(int k=1;k<=n;k++){
                sum=sum+fabs(y[k]-i);
            }
            ans=std::min(ans,sum);
        }
        printf("%d",ans);
    }
    
    
    • @ 2020-10-30 19:28:43

      朋友可真是太优秀了

  • 2
    @ 2016-07-14 16:21:59

    友情提示:读入方式不能freopen
    对Y坐标进行排序,选定一个坐标
    使其他Y坐标尽可能平均的分布在它的两侧
    原理:当油管以上和以下的点数量相等时,
    油管不穿过任何点时上下移动,总距离不变
    穿过任何的点都会增加距离
    所以上下点数量相等时为最短
    #include <cstdio>
    #include <algorithm>

    int abs(int x){
    if(x>0)
    return x;
    else
    return -1*x;
    }

    int main(){
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    int n,a[10001],refer,sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%*d%d",&a[i]);
    std::sort(a+1,a+n+1);

    if(n%2==0)
    refer=a[n/2];
    else
    refer=a[(n+1)/2];
    for(int i=1;i<=n;i++)
    sum+=abs(refer-a[i]);
    printf("%d",sum);
    return 0;
    }

  • 1
    @ 2020-12-16 20:57:08
    #include<bits/stdc++.h>
    using namespace std;
    int n,x,a[100001],ans,l;
    int main() 
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>x>>a[i];
        sort(a+1,a+n+1);
        l=n/2;
        for(int i=1;i<=l;i++) 
            ans+=a[n-i+1]-a[i];
        cout<<ans;
        return 0;
    }
    
  • 1
    @ 2020-10-14 14:11:31
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    namespace dts
    {
        int n,ans,a[10000];
        
        void main()
        {
            scanf("%d",&n);
            for (int i=0,temp;i<n;i++)
                scanf("%d%d",&temp,&a[i]);
            sort(&a[0],&a[n]);
            ans=0;
            for (int i=0,temp=a[n>>1];i<n;i++)
                ans+=(int)abs(a[i]-temp);
            printf("%d\n",ans);
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 1
    @ 2020-02-08 10:33:52

    到最南和最北的距离之和不变,所以,不断计算差,再求和就行。

    #include<iostream>
    using namespace std;
    int main()
    {
        int N, x, y[10000], sum = 0;
        cin >> N;
        for (int i = 0; i < N; i++)cin >> x >> y[i];
        for (int i = 0; i < N - 1; i++)for (int j = i + 1; j < N; j++)if (y[i] > y[j])
        {
            int temp = y[i];
            y[i] = y[j];
            y[j] = temp;
        }
        for (int i = 0; i < N / 2; i++)sum += y[N - i - 1] - y[i];
        cout << sum;
        return 0;
    }
    
  • 1
    @ 2019-05-26 18:16:37
    #include<stdio.h>
    #include<string.h>
    #include<math.h>
    void qsort(int a[],int l,int r)
    {
        int i=l,j=r,mid=a[(l+r)/2],b;
        while(i<=j)
        {
            while(a[i]<mid)i++;
            while(a[j]>mid)j--;
            if(i<=j)
            {
                b=a[i];
                a[i]=a[j];
                a[j]=b;
                i++;
                j--;
            }
        }
        if(l<j)qsort(a,l,j);
        if(r>i)qsort(a,i,r);
    } 
    int main()
    {
        int a[10005]={0},b,i,j,n,sum=0,min=210000000;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        scanf("%d%d",&b,&a[i]); 
        qsort(a,1,n);
        for(i=1;i<=n;i++) 
        {
            for(j=1;j<=n;j++)
            {
                if(a[i]>=a[j])
                sum=sum+(a[i]-a[j]);
                else
                sum=sum-(a[i]-a[j]);
            }
            min=sum;
            sum=0;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(a[i]>=a[j])
                sum=sum+(a[i]-a[j]);
                else
                sum=sum-(a[i]-a[j]);
            }
            if(sum<=min)
            min=sum;
            sum=0;
        }
        printf("%d",min); 
        return 0;
    }
    
  • 1
    @ 2018-03-22 19:23:34

    刚开始没看清题。。以为是求费马点,多写了一大堆关于x坐标的代码:)

    #include <stdio.h>
    #include <stdlib.h>
    #ifndef INDEX_I
    int index_i=0;
    #define INDEX_I
    #endif
    #define mapTo(data,n,type,function_body)\
        index_i=0;\
        for(;index_i<n;index_i++){\
            type x=data[index_i];\
            type * str_x=&data[index_i];\
            function_body;\
        }
    #ifndef RANGE_I
    int range_i=0;
    #define RANGE_I
    #endif
    #define for_range(x)\
        range_i=0;\
        for(;range_i<x;range_i++)
    #define bigger(x,y) ((x)>(y)?(x):(y))
    #define smaller(x,y) ((x)<(y)?(x):(y))
    #define abs(x) ((x)<0?(-(x)):(x))
    int readInt(){
        int n=0;
        scanf("%d",&n);
        return n;
    }
    void fillInData(int * data,int n){
        for_range(n) data[range_i]=readInt();
    }
    int avg(int * data,int n){
        int sum=0;
        mapTo(data,n,int,sum+=x);
        return sum/n;
    }
    typedef struct{
        int x,y;
    } point;
    int main(){
        
        int n=readInt();
        point data[10000];
        point point_max,point_min;
        point_max.x=point_max.y=-10001;
        point_min.x=point_min.y=10001;
        //刚开始没读清题,以为是寻找费马点的问题。。。多写了很多无用代码
        for_range(n){
            data[range_i].x=readInt();
            data[range_i].y=readInt();
            point_max.y=bigger(data[range_i].y,point_max.y);
            point_min.y=smaller(data[range_i].y,point_min.y);
        }
        int test_y;
        //玄学,加一个9多AC一条。。
        int smallest_distant=99999999;
        for(test_y=point_min.y;test_y<=point_max.y;test_y++){
            int sum=0;
            mapTo(data,n,point,{
                sum+=abs(x.y-test_y);
            });
            smallest_distant=smaller(sum,smallest_distant);
        }
        printf("%d",smallest_distant);
        return 0;
    }
    
  • 1
    @ 2017-12-13 14:11:36
    #include<bits/stdc++.h>
    int a[100010];
    int main() {
        int n, l, ans=0;
        scanf("%d", &n);
        for(int i=1; i<=n; i++) {
            int x;
            scanf("%d%d", &x, &a[i]);
        }
        std::sort(a+1,a+n+1);
        l=n/2;
        for(int i=1; i<=l; i++) ans+=a[n-i+1]-a[i];
        printf("%d", ans);
        return 0;
    }
    
  • 1
    @ 2017-10-04 12:46:16

    依稀还记得绝对值的几何意义,‘画’数轴秒杀。
    #include <iostream>
    #include <algorithm>
    using namespace std;

    int n,temp;
    int arr[10005];
    int ans=0;

    int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
    cin>>temp>>arr[i];
    }
    sort(arr+1,arr+n+1);
    if(n%2==0){
    temp=arr[n/2];
    for(int i=1;i<n/2;i++){
    ans+=temp-arr[i];
    }
    for(int i=n/2+1;i<=n;i++){
    ans+=arr[i]-temp;
    }
    }else{
    temp=arr[n/2+1];
    for(int i=1;i<n/2+1;i++){
    ans+=temp-arr[i];
    }
    for(int i=n/2+2;i<=n;i++){
    ans+=arr[i]-temp;
    }
    }
    cout<<ans;
    return 0;
    }

  • 1
    @ 2017-10-02 18:33:40

    桶排过了

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int n,y[10000]={0},ans=0,x;
    short book[20001]={0},f=0;
    void read(int &x)
    {
        int f=1;x=0;char s=getchar();
        while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
        while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
        x*=f;
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {read(x);read(y[i]);}
        for(int i=0;i<n;i++)
            book[y[i]+10000]++;
        for(int i=0;i<=20000;i++)
        {
            f+=book[i];
            if(f>n/2)
            {
                x=i-10000;
                break;
            }
        }
        for(int i=0;i<n;i++)
            ans+=abs(y[i]-x);
        cout<<ans;
        return 0;
    }
    
  • 1
    @ 2017-08-19 14:26:15
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    
    int main() {
        int n, a[10001], r = 0, junk;
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%d %d", &junk, &a[i]);
            
        std::sort(a, a + n);
        int m = a[n / 2];
        for(int i = 0; i < n; i++)
            r += abs(a[i] - m);
        printf("%d", r);
        return 0;
    }
    
  • 0
    @ 2020-02-07 17:05:25

    用了类似快排的方法,但是只排“一半”,求中位数的期望复杂度为O(n)。(不过这题似乎没必要这样写

    #include <cstdio>
    #include <iostream>
    #include <cstdlib>
    #include <algorithm>
    #include <cmath>
    #define MAXN 10010
    
    using namespace std;
    
    int x_arr[MAXN], y_arr[MAXN];
    int arr[MAXN], n;
    
    int my_rand(int l, int r) {
        srand(rand());
        return (int)rand() % (r - l) + l;
    }
    
    void print_arr() {
        for(int i = 0;i < n;++i) {
            printf("%d ", arr[i]);
        }
        putchar('\n');
    }
    
    int select_mediate(int l, int r) {
        int pivot = my_rand(l, r);
        // printf("pivot: %d -- %d\n", pivot, arr[pivot]);
        swap(arr[pivot], arr[r-1]);
        // print_arr();
        int i = l, j = l-1;
        for(;i < r;++i) {
            if(arr[i] <= arr[r-1]) {
                swap(arr[++j], arr[i]);
            }
            // printf("i: %d\tj: %d\n", i, j);
            // print_arr();
        }
        if(j < n/2) {
            return select_mediate(j, r);
        }
        else if(j > n / 2) {
            return select_mediate(0, j);
        }
        else {
            if(n % 2 == 1) {
                return arr[j];
            }
            else {
                return (arr[j] + arr[j-1]) / 2;
            }
        }
    }
    
    int main() {
        srand(122);
        scanf("%d", &n);
        for(int i = 0;i < n;++i) {
            scanf("%d%d", x_arr+i, y_arr+i);
            arr[i] = y_arr[i];
        }
        int m = select_mediate(0, n);
        int ans = 0;
        for(int i = 0;i < n;++i) {
            ans += abs(y_arr[i] - m);
        }
        printf("%d", ans);
        return 0;
    }
    
  • 0
    @ 2019-10-15 23:47:34

    这题实际上就是:
    求数轴上任意一个数到数轴上给定的n个数距离之和的最小值
    不信自己捋捋

  • 0
    @ 2019-08-02 21:09:29

    不用去重,也是醉了

    def sum_abs(m):
        s_rt = 0
        for i_local in range(0, n):
            s_rt += abs(coord_y[i_local] - m)
        return s_rt
    
    
    n = int(input())
    
    coord_y = []
    for i in range(0, n):
        in_put = input().split()
        coord_y.append(int(in_put[1]))
    coord_y.sort()
    out_put = sum_abs(coord_y[int(n / 2)])
    print(out_put)
    
    
    
    
  • 0
    @ 2018-10-01 18:37:52
    #include <iostream>
    #include <cstdlib>
    #include <math.h>
    #include <algorithm>
    #define MAX 2147483647
    using namespace std;
    
    int main()
    {
        int n;
        cin>>n;
        int x,y[n];
        for(int i=0;i<n;i++)
            cin>>x>>y[i];
            
        /*暴力枚举
        int ma=-1,mi=MAX;
        for(int i=0;i<n;i++)
        {
            ma=max(ma,y[i]);
            mi=min(mi,y[i]);
        }
        int ans=MAX,temp;
        for(int i=mi;i<=ma;i++)
        {
            temp=0;
            for(int j=0;j<n;j++)
                temp+=abs(y[j]-i);
            ans=min(ans,temp);
        }
        */
        
        //贪心求中位数+快排
        sort(y,y+n);
        int medium=y[n/2];
        int ans=0;
        for(int i=0;i<n;i++)
            ans+=abs(y[i]-medium);
        
        cout<<ans<<endl;
        return 0;
    }
    
    //贪心求中位数+桶排序:
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <math.h>
    using namespace std;
    
    int main()
    {
        int b[20001];
        memset(b,0,sizeof(b));
        int n;
        cin>>n;
        int x,y[n];
        for(int i=0;i<n;i++)
        {
            cin>>x>>y[i];
            b[y[i]+10000]++;
        }
        int temp=0;
        int medium;
        for(int i=0;i<20001;i++)
        {
            temp+=b[i];
            if(temp>n/2)
            {
                medium=i-10000;
                break;
            }
        }
        int ans=0;
        for(int i=0;i<20001;i++)
            ans+=abs(i-10000-medium)*b[i];
        cout<<ans<<endl;
        return 0;
    }
    
  • 0
    @ 2017-12-20 14:32:59

    n = int(raw_input())
    a = [int(raw_input().split()[1]) for i in range(n)]
    a = sorted(a)
    pos = a[n / 2]
    print sum([abs(i - pos) for i in a])

  • 0
    @ 2017-12-02 18:07:15
    /*Tokgo*/
    /*
    我们假设一条输油管道的纵坐标为y
    此时输油管道上方的油田数量为a
    下方的油田数量为b
    考虑一下y+1后对长度和L的影响
    即L+=a-b;
    不难发现,
    当管道上下油田数量一样多时
    L取最小值
    */
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int x,y[10001];
    int L;
    int avr;
    int len(int a,int b){
        if(a>b) return a-b;
        else return b-a;
    }
    int main()
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;++i)
            cin>>x>>y[i];
        sort(y+1,y+n+1);
        avr=y[(n+1)/2];
        for(int i=1;i<=n;++i)
            L+=len(avr,y[i]);
        cout<<L;
        return 0;
    }
    
    
    
  • 0
    @ 2017-10-07 23:05:09

    绝对值之和的最小值有规律|a|+|b|>=|a+b|,找到规律之后就简单了。但是规律不好找啊
    python3
    #id1691.py
    n = int(input())
    lst=[]
    for i in range(n):
    lst.append( list(map(int,input().split())))
    lsty=[]
    for i in lst:
    lsty.append(i[1])
    lsty.sort()#对y值进行排序
    if n==1:
    result = 0
    elif n%2 == 0:
    result = abs(sum(lsty[:int(n/2)])-sum(lsty[int(n/2):]))#前半部分之和与后半部分之和的差
    else:
    result = abs(sum(lsty[:int((n-1)/2)])-sum(lsty[int((n+1)/2):]))#除去中间数之后前半部分与后半部分之差
    print(result)

信息

ID
1691
难度
3
分类
其他 | 排序贪心 点击显示
标签
(无)
递交数
3930
已通过
1851
通过率
47%
被复制
15
上传者