第六周作业

MT2108 外卖递送

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

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

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

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

备注
其中：对于 100% 的数据 1≤n≤100000,abs(ai)≤100000001≤n≤10 0000,abs(a_i )≤1000 00001≤n≤100000,abs(ai​)≤10000000。

相关知识点：排序、贪心

题解
本题模型来源于算法导论里的 “求 n 个点的最小距离” ，抽象出来是：已知一条直线上 $n$ 个点的横坐标，求直线上的一个点使得该点与其他所有点的距离之和最小。
根据这样的问题描述，可以建立其数学问题为：
已知升序序列 X={x1,x2,…,xn}X=\\{x_1,x_2,…,x_n\\}X={x1​,x2​,…,xn​} 中所有元素的值，试求 ∣x−x1∣+∣x−x2∣+……+∣x−xn∣|x-x_1|+|x-x_2|+……+|x-x_n|∣x−x1​∣+∣x−x2​∣+……+∣x−xn​∣ 的最小值及此时的 $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;
}

MT2109 奇偶序列

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

题目描述
给定 $n$ 个数的数组，奇数和偶数分别排序（即所有奇数的占位和偶数的占位不变）。

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

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

备注
1≤n≤10000,1≤ai≤1000001≤n≤10000,1≤a_i≤10 00001≤n≤10000,1≤ai​≤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 tmp, pos;// 根据 flag 的取值进行排序：for(int i=0;i<aryLen-1;i++){if(ary[i] % 2 == flag){tmp = ary[i];pos = i; }else continue;// 选择排序 for(int j=i+1;j<aryLen;j++){if((ary[j] % 2 == flag) && (ary[j] < tmp)){tmp = ary[j];pos = j;}}if(pos != i){ary[pos] = ary[i];ary[i] = tmp;}}
}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;
}

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;
}

题解 2
如果将一串字符串中的各字符视为数字（即 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;
}

MT2111 名次并列

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

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

格式
输入格式：第一行为两个正整数 $(1\le k\le n\le 1e5)$。
     第二行为 n 个正整数，分别表示参加比赛的人的分数 a1,a2,…,an(0≤ai≤100)a_1,a_2,…,a_n (0≤a_i≤100)a1​,a2​,…,an​(0≤ai​≤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;
}

MT2107 活动分组

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

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

格式
输入格式：第一行为一个偶数 n∈[2,1×105]n∈[2,1×10^5 ]n∈[2,1×105] 表示总人数；
     第二行为 $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;
}

END