【马蹄集】—— 排序专题_码题集小码哥组织一次团建活动

排序专题

---

MT2107 活动分组

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

小码哥组织一次团建活动，共有 $n$ 人参加。活动分为 A、B 两个项目，每个项目都需要两人组队参加。假设每个人有两个能力值 $a，b$ 分别表示对 A、B 两个项目的擅长程度，为了使活动圆满进行，小码哥希望每一组的两个人 A 能力值之和等于 B 能力值之和。请你帮忙计算是否有一种分组的可能满足小码哥的想法。

格式

输入格式：第一行为一个偶数 $n\in [2,1\times 10^5]$ 表示总人数；
     第二行为 $n$ 个正整数表示每个人 A 项目的能力值；
     第三行为 $n$ 个正整数表示每个人 B 项目的能力值；
输出格式：如果存在这样的分组输出 YES，否则输出 NO。

样例 1

输入：6
   1 2 3 4 5 6
   6 5 4 3 2 1
输出：YES

备注

第一个和第六个一组，第二个和第五个一组，第三个和第四个一组，这样每组的 A 项目能力值之和均为7，B 项目能力值之和均为7。

相关知识点：排序

题解

注意到：对于满足匹配条件的两个人而言，其中一人的 A、B 能力之差应与其匹配对象的 A、B 能力之差互反。
举个例子，假设某个对象 $i$ 的 A、B 能力分别为： $Person[i].A=24,Person[i].B=18$，则该对象的 A、B 能力之差 $Person[i].gap=24-18=6$;
那他的匹配对象 $Person[j]$ 要满足什么条件呢？很简单，只要 $Person[j].gap=-Person[i].gap=-6$ 即可。比如，$Person[j]$ 可以是：$Person[j].A=20,Person[j].B=26$；也可以是 $Person[j].A=10,Person[j].B=16$ ……
根据这样的思路，可以将求解本题的思路列出：

• 对输入的两个数组求差（为节约存储可以进行原地做差）；
• 对存放差值的数组进行排序；
• 从排序后的数组两端往中间进行扫描，每次各从一个端点取出一个数进行求和，若求和得到的结果为 0 则继续执行该步骤；否则表示存在无法匹配的情况（此时直接输出 NO 并终止程序）。
• 若能从上面的循环走出，表示该数据集存在至少一种组合方案，故输出 YES。

基于此，可直接写出以下代码（已 AC）:

/*
	活动分组 
	
	思路：对每个人而言，他的 A、B 能力之差应与其匹配对象的 A、B 能力之差互反 
*/

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

const int MAX = 100005;
int capacity[MAX][2];  
int capacityGap[MAX];

bool matchAntithesis(int ary[][2], int len)
{
	// 计算每个人的能力数组中，第一个元素与第二个元素的差值
	for(int i=0;i<len;i++) capacityGap[i] = ary[i][0]-ary[i][1];
	
	// 对差值数组排序
	sort(capacityGap,capacityGap+len);
	
	// 执行消融
	int l = 0, r = len-1;
	while(l<r){
		if(capacityGap[l] + capacityGap[r] == 0){
			l++;
			r--;
		}
		else return false;
	}
	return true;
}

int main( )
{
	// 录入数据 
	int n;cin>>n; 
	for(int i=0;i<2;i++)
		for(int j=0;j<n;j++) cin>>capacity[j][i];
		
	// 执行匹配 
	if(matchAntithesis(capacity,n)) cout<<"YES";
	else cout<<"NO";
	
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

---

MT2108 外卖递送

难度：钻石    时间限制：1秒    占用内存：64M

题目描述

小码哥又被安排去建设外卖站了，所有居民的居住地点 $a_i$ 都在一条 x 轴上，小码哥为了使送外卖移动的距离最短，现在在选择设置外卖站的位置。
小码哥请你帮忙计算把站建在何处，可以使得站到每家居民的距离之和最小?
注意：不保证居民的居住地点 $a_i$ 唯一，即可以两个居民的居住地点相同，允许外卖站设在居民点。

格式

输入格式：第一行一个整数 $n$，表示居民的居住地点个数；
     第二行 $n$ 个整数 $a_1$~ $a_n$。
输出格式：输出一个整数，表示距离之和的最小值。

样例 1

输入：4
   6 2 9 1
输出：12

备注

其中：对于 100% 的数据 $1\le n\le 100000,abs(a_i)\le 10000000$。

相关知识点：排序、贪心

题解

本题模型来源于算法导论里的 “求 $n$ 个点的最小距离” ，抽象出来是：已知一条直线上 $n$ 个点的横坐标，求直线上的一个点使得该点与其他所有点的距离之和最小。
根据这样的问题描述，可以建立其数学问题为：
已知升序序列 X = { x 1 , x 2 , … , x n } X=\{x_1,x_2,…,x_n\} X={x1​,x2​,…,xn​} 中所有元素的值，试求 $|x-x_1|+|x-x_2|+\dots \dots +|x-x_n|$ 的最小值及此时的 $x$值。
求解上式得到的结果表明：
x = { X 的中位数， n 为奇数时 X 中间两个数的任何实数 ( 包括这个两个数 ) ， n 为偶数时 x=

$$\begin{equation} \left\{ \begin{aligned} \nonumber & X 的中位数，n为奇数时\\ & X 中间两个数的任何实数(包括这个两个数)，n为偶数时\\ \end{aligned} \right. \end{equation}$$ x={​X的中位数，n为奇数时X中间两个数的任何实数(包括这个两个数)，n为偶数时​​
基于此，可写出以下代码（已 AC）：

/*
	MT2108 外卖递送
*/ 

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

const int MAX = 100005;
int ary[MAX]; 

int main( )
{
	
	int n, mid;
	long sum = 0;
	
	// 录入数据 
	cin>>n;
	for(int i=0;i<n;i++) cin>>ary[i];
	
	// 排序
	sort(ary,ary+n);
	
	// 获取 x 的索引 
	mid = n/2;
	
	// 求最小值
	for(int i=0;i<n;i++) sum += abs(ary[i]-ary[mid]);
	
	// 输出结果
	cout<<sum; 
	 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

MT2109 奇偶序列

难度：钻石    时间限制：1秒    占用内存：128M

题目描述

给定含 $n$ 个数的数组，现要求对其中的奇数和偶数分别排序（即所有奇数的占位和偶数的占位不变）。

格式

输入格式：第一行输入一个正整数 $n$；
     第二行输入 $n$ 个整数 $a_i$ 。
输出格式：输出排好序的数组。

样例 1

输入：5
   3 4 1 5 2
输出：1 2 3 5 4

备注

$1\le n\le 10000,1\le a_i\le 100000$

相关知识点：排序

题解

该题是这周最简单的一道题，没什么难度，我的求解方式是自己写了个带参的排序函数（此参数用于限制对奇偶位的排序）。代码如下：

/*
	奇偶序列 
	
	思路：分别排序即可 
*/

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

const int MAX = 10005;
int ary[MAX]; 

// 选择法排序 
// 此函数将根据 flag 的取值分别对奇、偶数位上的数字进行排序：保持奇数和偶数的占位不变 
// flag=true 时对奇数位执行排序 
// flag=false 时对奇数位执行排序 
void sortSubjectOdd(int ary[], int aryLen, bool flag)
{
    int pos;
    // 根据 flag 的取值进行排序：
    for(int i=0;i<aryLen-1;i++){
        if((ary[i] & 1) == flag) pos = i; 
        else continue;
        
        // 选择排序 
        for(int j=i+1;j<aryLen;j++){
            if(((ary[j] & 1) == flag) && (ary[j] < ary[pos]))
                pos = j;
        }

        // 不等则发生交换
        if(pos != i) swap(ary[i], ary[pos]);
    }
}

void sortRespectively(int ary[], int aryLen){
    // 对偶数排序 
    sortSubjectOdd(ary,aryLen,false);
    
    // 对奇数排序 
    sortSubjectOdd(ary,aryLen,true);
}

// 打印数组内容 
void printArt(int ary[], int aryLen) {
    for(int i=0;i<aryLen;i++) cout<<ary[i]<<" ";
}

int main( )
{
    // 获取输入 
    int n;cin>>n;
    for(int i=0;i<n;i++) cin>>ary[i]; 
    
    // 处理数据
    sortRespectively(ary,n);
    
    // 执行输出 
    printArt(ary,n);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

---

MT2110 sort

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

或许在某个平行宇宙存在一种语言，使用的字母和英语一样，但字典序不一样。
给出1个字典序和1个字符串，将字符串按新字典序排序。

格式

输入格式：第一行26个互不相同的小写字母，表示新型字典序；
     第二行1个字符串，表示待排序字符串。
输出格式：1个字符串代表答案。

样例 1

输入：qwertyuiopvmnbcxzasdfghjkl
   peace
输出：eepca

备注

其中：$1\le 字符串长度\le 10000，字符串只包含小写字母$。

相关知识点：排序

题解

方法一

按给定字典序对指定字符串进行排序可通过二重循环完成：

• 第一重循环用以扫描新的字典序；
• 第二重循环用以扫描给定的字符串（特别注意：一定要逆序扫，这样在重排给定字符串的过程中，当发生位置交换时，能保证被换的字符一定是会被放在后面的字符）。同时，这里还有一个技巧。在逆序扫描给定字符串时，只要发生了交换，则被换到前列的字符就一定是固定死了的，因此可以额外定义一个从前往后移动的指针 pos ，一旦 pos 的取值与字符串的长度相等时就表示当前字符串已经完成了排序。

基于以上思路可写出以下 AC 代码：

/*
	sort
	算法 1
*/

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

// 定义字典序的总长度 
const int N=26;
const int MAX = 100005;
char dict[N]; 
char str[MAX];

void sortStr(char str[], char dict[])
{
	// 获取输入字符串的长度
	int strLen = 0, pos = 0;
	while(str[strLen]) strLen++;
	
	// 扫描字典序 
	for(int i=0; i<N;i++){
		
		// 扫描给定字符串（逆序） 
		for(int j = strLen-1; j>=pos; j--){
			
			// 判断当前字符是否与字典序中的当前字符一致，是就需要考虑与前面的字符交换位置 
			if(str[j] == dict[i]){
				
				// 若待交换位置的字符与当前字符一致，则待交换位置后移 
				while(pos<j && str[pos] == dict[i]) pos++;
				
				// 发生交换 
				swap(str[j],str[pos++]);
			}
		}
		
		// 判断前向指针是否已经走到给定字符串的尽头 
		if(pos == strLen) break;
	} 
}

int main( )
{
	// 获取输入 
	cin>>dict;
	cin>>str;
	
	// 处理数据
	sortStr(str,dict);
	
	// 执行输出 
	cout<<str;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

方法二

如果将一串字符串中的各字符视为数字（即 ASCII值），那么对字符串的排序是不是就转换为对数组的排序了呢？
从这样的角度出发，如果能将给定的字典序转换为某种排序规则的话，我们就能直接利用 STL 库中的函数直接对字符串进行排序。
于是这里我定义了一个 newsqe[ ] 数组用以存放新输入的字典序。其定义规则为：newsqe 的索引是新字典序中某各字符与 ‘a’ 的差值，对应存放的值为当前字符的顺序。这样一来，就相当于构建了一个指示 char 序列中的顺序的数组，根据这个数组，我们可定义相关的 cmp 函数，以完成对 STL 中 sort 函数的调用。
采用这一的思路完成的代码如下（已 AC）：

/*
	sort
	算法 2
*/

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

const int N=26;
const int MAX = 100005;

// 定义新字典 
char dict[N];

// 定义待输入字符串 
char str[MAX];

// 定义新字典中的字符顺序（完成从 char 到 int 的映射）
int newsqe[N]; 

// 自定义排序规则
bool cmp(char a, char b){
	return newsqe[a-'a'] < newsqe[b-'a']; 
} 

int main() 
{
	// 获取输入 
	cin>>dict;
	cin>>str;
	
	// 为输入的字典构建新的顺序
	for(int i=0;i<N;i++) newsqe[dict[i]-'a'] = i;
	
	// 根据新的字典顺序对输入字符串进行排序 
	sort(str,str+strlen(str),cmp);
	
	// 执行输出 
	cout<<str;
	
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---

MT2111 名次并列

难度：钻石    时间限制：1秒    占用内存：128M

题目描述

有 $n$ 个人参加比赛，其中分数排名前 $k$ 的人将被选入下一轮（选入下一轮的人分数必须为正）。特别的，如果几个人分数相同且刚好并列处于第 $k$ 名，则这几个人都将被选入下一轮；若存在并列第 $k-i$ 名，但是全部算入后选入下一轮的人数超过 $k$ 人，则排名在第 $k-i$ 名后的所有人将都不能进入下一轮。小码哥请你输出进入下一轮的人数？

格式

输入格式：第一行为两个正整数 $(1\le k\le n\le 1e5)$。
     第二行为 n 个正整数，分别表示参加比赛的人的分数 $a_1,a_2,\dots ,a_n(0\le a_i\le 100)$。
输出格式：1 个正整数，表示进入下一轮的人数。

样例 1

输入：8 5
   7 5 10 7 9 8 7 5
输出：6

相关知识点：排序

题解

这道题确实在考察排序，但其更像是一道 “模拟” 类型的题，整体没什么难度，还是非常简单的。下面直接给出 AC 代码

/*
	名次并列
*/

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

const int MAX = 100005;
int scores[MAX];  ;

int getNextRoundPersons(int ary[], int n, int k)
{
	// 排序
	sort(ary,ary+n);
	
	// lastScore 表示前一位的分数， iPos 表示当前有多少名次 ， nextRoundPersons表示进入下一轮的人数 
	int lastScore = ary[n-1], iPos = 1, nextRoundPersons = (lastScore!=0);	
	
	// 筛选进入下一轮的人数 
	for(int i=n-2;i>=0;i--){
		// 杜绝 0 分选手获奖的情况 
		if(ary[i] ==0 ) break;
		
		// 如果当前的名次数已经超过 k，则退出循环 
		if(iPos > k) break;
		
		// 分数不同时，更改上一次的计分，并将名次序列号增加 
		if(ary[i] != lastScore){
			lastScore = ary[i];
			iPos++;
			
			// 若此时 nextRoundPersons 已经达到 k，则人数就已经满了 
			if(nextRoundPersons == k) break;
		}
		
		// 进入下一轮的人数 +1 
		nextRoundPersons++;
	}
	
	return nextRoundPersons;
} 

int main( )
{
	// 录入数据 
	int n, k;
	cin>>n>>k; 
	for(int i=0;i<n;i++) cin>>scores[i];
		
	// 计算并输出下一轮人数 
	cout<<getNextRoundPersons(scores, n, k);
	
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

END

---