中位数应用-货仓选址-纸牌均分-糖果传递-七夕祭

妖狐艹你老母 2022-03-20 16:50 335阅读 0赞

## 1. 货仓选址 ##

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

**输入格式**  
第一行一个整数N，第二行N个整数A\[1\]~A\[N\]。

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

**样例输入**  
4  
6 2 9 1  
**样例输出**  
12  
**数据范围与约定  
对于100%的数据: N<=100000, A\[i\]<=1000000**

**问题分析：**  
直观的想，假设我们将货仓建在第k个商店的坐标上，那么货仓左边有 k - 1 个商店，右边有 n - k - 1 个商店，当我们将货仓向右移动一个单位，那么货仓距离左面所有的商店的距离就会增加一个单位，距离右面所有的商店的距离会减少一个单位，所以应当使左右商店的个数相同， k-1 = n-k-1, 那么k=n/2, k就是整个序列中位数的位置。

**代码：**

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int a[N];
    
    int main()
    {
        
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; i++)
    		cin >> a[i];
    	
    	sort(a, a + n);
    	
    	int spc = a[n >> 1];
    	int res = 0;
    	
    	for (int i = 0; i < n; i++)
    		res += abs(a[i] - spc);
    	
    	cout << res << endl;
    }

## 2. 均分纸牌 ##

**问题描述：**  
【该问题是我自己编的，只是说一下大体的题意】有N堆牌， 每次只能向相邻的牌堆移动一张牌，给定N堆牌的数目，问至少需要移动多少次使各个牌堆的牌数相同？

**问题分析：**  
首先，我们知道总牌数一定可以被N整除，否则没有解，平均数mid就是最后每堆牌到达的一个状态，对于第一堆来说，当a\[1\] < mid 时，只能从第二堆拿，补到mid张；当a\[1\] > mid时，只能把多余的给第二堆；当a\[1\] = mid时，不需要动；对于所有堆，多退少补。  
假设 A A A是 a a a的前缀和，即 A \[ i \] = ∑ j = 1 i a \[ j \] A\[i\] = \\sum\_\{j=1\}^ia\[j\] A\[i\]=∑j=1ia\[j\]，那么总移动次数= ∑ i = 1 N ∣ i ∗ m i d − A \[ i \] ∣ \\sum\_\{i=1\}^N|i\*mid-A\[i\]| ∑i=1N∣i∗mid−A\[i\]∣  
这里有个小技巧，我们最后的目标是让整个 a a a序列都成为等于mid，这样的话，我们可以事先先都减去一个mid，那么我们最后的目标就成为让整个 a a a序列都变成0，总移动次数= ∑ i = 1 N A \[ i \] \\sum\_\{i=1\}^NA\[i\] ∑i=1NA\[i\]，我们可以发现，都减去一个mid后，答案就是a序列的前缀和再求和。  
**代码：**

#include <iostream>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 100010;
    
    int a[N];
    
    int main()
    {
        
    	memset(a, 0, sizeof(a));
    
    	int n;
    	ll sum = 0;
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    	{
        
    		cin >> a[i];
    		sum += a[i];
    	}
    	int mid = sum / n;
    	ll res = 0;
    	for (int i = 1; i <= n; i++)
    	{
        
    		a[i] -= mid;
    		a[i] += a[i - 1];
    	}
    
    	for (int i = 1; i <= n; i++)
    		res += abs(a[i]);
    
    	cout << res << endl;
    }

## 3. 糖果传递 ##

**问题描述：**  
有n个小朋友坐成一圈，每人有a\[i\]个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为1。

求使所有人获得均等糖果的最小代价。

**输入格式**  
第一行输入一个正整数n，表示小朋友的个数。

接下来n行，每行一个整数a\[i\]，表示第i个小朋友初始得到的糖果的颗数。

**输出格式**  
输出一个整数，表示最小代价。

**数据范围  
1≤n≤1000000**

**时/空限制： 2s / 64MB**

**输入样例：**  
4  
1  
2  
5  
4  
**输出样例：**  
4

**问题分析：**

这个和刚才的均分纸牌相比，这是一个环形的均分纸牌问题，我们看看他们有什么联系。  
首先一定存在一种最优解使得某两个人之间没有纸牌交换。就是要么a给b，要么b给a，不能a给了b，b又给了a，如果存在这样的交换，就不是最优解了，可以用反证法证明。  
假设我们从第 k k k个位置断开,那么序列就变成了：  
 a \[ k + 1 \] = A \[ k + 1 \] − A \[ k \] a\[k+1\] = A\[k+1\]-A\[k\] a\[k\+1\]=A\[k\+1\]−A\[k\]  
 a \[ k + 1 \] = A \[ k + 2 \] − A \[ k \] a\[k+1\] = A\[k+2\]-A\[k\] a\[k\+1\]=A\[k\+2\]−A\[k\]  
 . . . ... ...  
 a \[ N \] = A \[ N \] − A \[ k \] a\[N\]=A\[N\]-A\[k\] a\[N\]=A\[N\]−A\[k\]  
 a \[ 1 \] = A \[ 1 \] + A \[ N \] − A \[ k \] a\[1\]=A\[1\]+A\[N\]-A\[k\] a\[1\]=A\[1\]\+A\[N\]−A\[k\]  
 a \[ 2 \] = A \[ 2 \] + A \[ N \] − A \[ k \] a\[2\]=A\[2\]+A\[N\]-A\[k\] a\[2\]=A\[2\]\+A\[N\]−A\[k\]  
 a a a序列的每一项都减去了mid， A \[ N \] ( 第 n 项 的 前 缀 和 ) A\[N\](第n项的前缀和) A\[N\](第n项的前缀和)一定等于0，那么变成了：  
 a \[ k + 1 \] = A \[ k + 1 \] − A \[ k \] a\[k+1\] = A\[k+1\]-A\[k\] a\[k\+1\]=A\[k\+1\]−A\[k\]  
 a \[ k + 1 \] = A \[ k + 2 \] − A \[ k \] a\[k+1\] = A\[k+2\]-A\[k\] a\[k\+1\]=A\[k\+2\]−A\[k\]  
 . . . ... ...  
 a \[ N \] = A \[ N \] − A \[ k \] a\[N\]=A\[N\]-A\[k\] a\[N\]=A\[N\]−A\[k\]  
 a \[ 1 \] = A \[ 1 \] − A \[ k \] a\[1\]=A\[1\]-A\[k\] a\[1\]=A\[1\]−A\[k\]  
 a \[ 2 \] = A \[ 2 \] − A \[ k \] a\[2\]=A\[2\]-A\[k\] a\[2\]=A\[2\]−A\[k\]  
我们要枚举k，使得 ∣ A \[ 1 \] − A \[ k \] ∣ + ∣ A \[ 2 \] − A \[ k \] ∣ + . . . + ∣ A \[ n \] − A \[ k \] ∣ |A\[1\]-A\[k\]|+|A\[2\] - A\[k\]|+...+|A\[n\]-A\[k\]| ∣A\[1\]−A\[k\]∣\+∣A\[2\]−A\[k\]∣\+...\+∣A\[n\]−A\[k\]∣总和最小，现在我们可以发现，这其实就是我们刚才说的货舱选址问题， A \[ k \] A\[k\] A\[k\]是货仓的位置， ∣ A \[ i \] − A \[ k \] ∣ |A\[i\]-A\[k\]| ∣A\[i\]−A\[k\]∣是第i个商店和货仓之间的距离，这样我们就不需要枚举 k k k，可以直接得出， A \[ k \] A\[k\] A\[k\]就是整个序列的中位数。  
over！！！

**代码：**

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1000010;
    
    typedef long long ll;
    
    ll a[N];
    
    int main()
    {
        
        ll n;
        cin >> n;
        a[0] = 0;
        ll sum = 0;
        for(int i = 1;i <= n;i++){
        
            cin >> a[i];
            sum += a[i];
        }
        ll mid = sum / n;
        for(int i = 1;i <= n;i++){
        
            a[i] -= mid;
            a[i] += a[i - 1];
        }
        sort(a + 1, a + n + 1);
        ll spc = a[n >> 1];
        ll res = 0;
        for(int i = 1;i <= n;i++)
            res += abs(a[i] - spc);
        cout << res << endl;
    }

## 4. 七夕祭 ##

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是TYVJ今年举办了一次线下七夕祭。

Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。

TYVJ七夕祭和11区的夏祭的形式很像。

矩形的祭典会场由N排M列共计N×M个摊点组成。

虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。

不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。

由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在Vani想知道他的两个要求最多能满足多少个。

在此前提下，至少需要交换多少次摊点。

**输入格式**  
第一行包含三个整数N和M和T，T表示cl对多少个摊点感兴趣。

接下来T行，每行两个整数x, y，表示cl对处在第x行第y列的摊点感兴趣。

**输出格式**  
首先输出一个字符串。

如果能满足Vani的全部两个要求，输出both；

如果通过调整只能使得各行中cl感兴趣的摊点数一样多，输出row；

如果只能使各列中cl感兴趣的摊点数一样多，输出column；

如果均不能满足，输出impossible。

如果输出的字符串不是impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。

**数据范围**  
1≤N,M≤100000,  
0≤T≤min(N∗M,100000),  
1≤x≤N,  
1≤y≤M

**时/空限制： 1s / 64MB**

**输入样例：**  
2 3 4  
1 3  
2 1  
2 2  
2 3  
**输出样例：**  
row 1

**问题分析：**  
行、列各进行一次糖果传递问题就结束了。  
**代码：**

#include <iostream>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 100010;
    
    int cols[N];
    int rows[N];
    
    int main()
    {
        
        memset(cols, 0, sizeof(cols));
        memset(rows, 0, sizeof(rows));
        
        int n, m, t;
        cin >> n >> m >> t;
        
        ll sumcol = 0, sumrow = 0;
        for(int i = 1, a, b;i <= t;i++){
        
            cin >> a >> b;
            cols[a] ++;
            rows[b] ++;
            sumcol ++;
            sumrow ++;
        }
        bool iscol = sumcol % n == 0;
        bool isrow = sumrow % m == 0;
        int midcol = sumcol / n;
        int midrow = sumrow / m;
        ll res = 0;
        if(iscol){
        
            for(int i = 1;i <= n;i++){
        
                cols[i] -= midcol;
                cols[i] += cols[i - 1];
            }
            sort(cols + 1, cols + 1 + n);
            int spccol = cols[n + 1 >> 1];
            for(int i = 1;i <= n;i++){
        
                res += abs(spccol - cols[i]);
            }
        }
        if(isrow){
        
            for(int i = 1;i <= m;i++){
        
                rows[i] -= midrow;
                rows[i] += rows[i - 1];
            }
            sort(rows + 1, rows + 1 + m);
            int spcrow = rows[m + 1 >> 1];
            for(int i = 1;i <= m;i++){
        
                res += abs(spcrow - rows[i]);
            }
        }
        if(iscol || isrow){
        
            if(iscol && isrow){
        
                cout << "both" << " ";
            }
            else if(iscol){
        
                cout << "row" << " ";
            } 
            else{
        
                cout << "column" << " ";
            }
            cout << res << endl;
        }
        else
            cout << "impossible" << endl;
    }