智商恢复训练(中位数)

我会带着你远行 2021-09-18 00:06 332阅读 0赞

在一个有序序列里，中位数有一些很优美的性质。

**1**  
**货仓选址**  
在一条数轴上有 N N N家商店，它们的坐标分别为  A 1 … A N A\_1…A\_N A1…AN。  
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

我们设在仓库左边的点有p个,右边的有q个，若p < q,当仓库向右移动的话，距离之和会减少，如p＞q ,当仓库向左移动的话，距离之和会减少，所以说当p = q时为最优解。因此货仓建在中位数处。

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    
    typedef long long ll;
    
    const int maxn = 100000+1000;
    
    int n;
    int a[maxn];
    int main(int argc, char const *argv[])
    { 
    	scanf("%d",&n);
    	rep(i,0,n)
    	{ 
    		scanf("%d",&a[i]);
    	}
    	sort(a,a+n);
    	int mid = a[(n+1)/2];
    	ll ans = 0;
    	rep(i,0,n)
    	{ 
    		ans += abs(a[i] - mid);
    	}
    	printf("%lld\n",ans);
    	return 0;
    }

**均分纸牌**  
有 N N N堆纸牌，编号分别为  1 , 2 , … , N 1,2,…,N 1,2,…,N。每堆上有若干张，但纸牌总数必为 N N N的倍数。可以在任一堆上取若干张纸牌，然后移动。  
移牌规则为：在编号为 1 1 1堆上取的纸牌，只能移到编号为 2 2 2的堆上；在编号为 N N N的堆上取的纸牌，只能移到编号为 N − 1 N-1 N−1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。  
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

假如每次只能移动一个  
 a n s = ∑ i = 1 N ∣ S \[ i \] ∣ ans = \\sum\_\{i = 1\}^\{N\}|S\[i\]| ans=∑i=1N∣S\[i\]∣ 其中S是A的前缀和 s \[ i \] = ∑ j = 1 i A \[ j \] s\[i\] = \\sum\_\{j=1\}^\{i\}A\[j\] s\[i\]=∑j=1iA\[j\]  
 A \[ i \] = c \[ i \] − T / N A\[i\] = c\[i\]-T/N A\[i\]=c\[i\]−T/N  
对于这题，只需要判断 S \[ i \] S\[i\] S\[i\]不等于0的情况加一

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    typedef long long ll;
    
    const int maxn = 1e3;
    
    int n;
    int a[maxn];
    int f[maxn];
    int main(int argc, char const *argv[])
    { 
    	scanf("%d",&n);
    	ll sum = 0;
    	ll ans = 0;
    	rep(i,1,n+1)
    	{ 
    		scanf("%d",&a[i]);
    		sum += a[i];
    	}
    	sum /= n;
    	// printf("%lld\n",sum);
    	rep(i,1,n+1)
    	{ 
    		a[i] -= sum;
    		f[i] = f[i-1] + a[i];
    		if(!f[i]) continue;
    		ans++;
    	}
    	// rep(i,1,n+1)
    	// { 
    	// ans += abs(f[i]);
    	// }
    	printf("%lld\n",ans );
    	return 0;
    }

**BZOJ 1045 环形均分纸牌**  
想普通的均分纸牌，断一下就能得到答案  
 a n s = ∑ i = 1 N ∣ S \[ i \] − S \[ k \] ∣ ans = \\sum\_\{i = 1\}^\{N\}|S\[i\]-S\[k\]| ans=∑i=1N∣S\[i\]−S\[k\]∣  
需要枚举K吗？想一想第一个题， S \[ k \] S\[k\] S\[k\]为中位数时最优  
注意此题的数据范围

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    typedef long long ll;
    
    const int maxn = 1000005+100;
    
    int n;
    int a[maxn];
    int main(int argc, char const *argv[])
    { 
    	scanf("%d",&n);
    	ll sum = 0;
    	rep(i,1,n+1)
    	{ 
    		scanf("%d",&a[i]);
    		sum += a[i];
    	}
    	sum /= n;
    
    	rep(i,1,n+1)
    	{ 
    		a[i] -= sum;
    		a[i] += a[i-1];
    	}
    	sort(a+1,a+n+1);
    	ll mid = a[(n+1)/2];
    	ll ans = 0;
    	rep(i,1,n+1)
    	{ 
    		ans += abs(a[i]-mid);
    	}
    	printf("%lld\n",ans);
    	return 0;
    }

**\[BZOJ3032\]七夕祭（中位数）**  
分割成行和列两个独立的子问题

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    typedef long long ll;
    
    const int maxn=100010;
    
    int x[maxn],y[maxn],s1[maxn],s2[maxn];
    
    int n,m,T;
    int a,b;
    int main(int argc, char const *argv[])
    { 
        scanf("%d%d%d",&n,&m,&T);
    
        rep(i,1,T+1)
        { 
            scanf("%d%d",&a,&b);
            x[a]++,y[b]++;
        }
        if(T%m!=0 && T%n!=0)
        { 
            printf("impossible\n");
            return 0;
        }
        rep(i,1,n+1) x[i]-=T/n;
        rep(i,1,m+1) y[i]-=T/m;
        ll ans=0;
        if(T%n==0)
        { 
            rep(i,1,n+1) 
            s1[i]=s1[i-1]+x[i];
            sort(s1+1,s1+n+1);
            ll mid=s1[(n+1)/2];
            rep(i,1,n+1)
                ans+=abs(s1[i]-mid);
        }
        if(T%m==0)
        { 
            rep(i,1,m+1)
            s2[i]=s2[i-1]+y[i];
            sort(s2+1,s2+m+1);
            ll mid=s2[(m+1)/2];
            rep(i,1,m+1)
                ans+=abs(s2[i]-mid);
        }
        if(T%n==0 && T%m==0) 
            printf("both ");
        else if(T%n==0 && T%m!=0) 
            printf("row ");
        else 
            printf("column ");
        printf("%lld\n",ans);
        return 0;
    }