# NENUOJ 之 算法2排序B
# 前言
不太好写的一章节~愿读者充满耐心地学习每一道题，如果是面对小测，可以提前准备一下，因为这一章不太容易在初次见到的时候马上做出来。
# B001 快乐的蠕虫 (opens new window)
# 题目描述
有一只快乐的蠕虫居住在一个m×n大小的网格中。在网格的某些位置放置了k块石头。网格中的每个位置要么是空的，要么放置了一块石头。当蠕虫睡觉时，它在水平方向或垂直方向上躺着，把身体尽可能伸展开来。蠕虫的身躯既不能进入到放有石块的方格中，也不能伸出网格外。而且蠕虫的长度不会短于2个方格的大小。 本题的任务是给定网格，要计算蠕虫可以在多少个不同的位置躺下睡觉。
# 输入
输入文件的第1行是一个整数t，1<=t<=11,表示测试数据的个数。每个测试数据的第1行为3个整数：m,n和k(0<=m,n,k<=200000),接下来有k行，每行为2个整数，描述了一块石头的位置（行和列，最左上角位置为（1,1））。
# 输出
对每个测试数据，输出占一行，为一个整数，表示蠕虫可以躺着睡觉的不同位置的数目。
# 样例输入 复制
1 5 5 6 1 5 2 3 2 4 4 2 4 3 5 1# 样例输出 复制
9
# 思路：
笔者觉得这题挺难写的，基本思路就是把网格四周一圈也当作石头，然后在内部通过x轴排序还有y轴排序的方式，分别去放蠕虫，然后计数，虽然很不喜欢这道题，但是好像考试考的概率特别大【悲】愿读者自求多福。
# 代码C++：
#include<bits/stdc++.h>
using namespace std;
typedef struct stone{
int x;
int y;
}s;
s st[200007];
bool cmp1(s a,s b){
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
bool cmp2(s a,s b){
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
void solve(){
int m,n,k;
cin >> m >> n >> k;
int cnt = 0;
for(int i = 0;i <= n + 1;i++){
st[cnt].x = 0,st[cnt].y = i;
cnt++;
st[cnt].x = m + 1,st[cnt].y = i;
cnt++;
}
for(int i = 0;i <= m + 1;i++){
st[cnt].x = i,st[cnt].y = 0;
cnt++;
st[cnt].x = i,st[cnt].y = n + 1;
cnt++;
}
for(int i = 1;i <= k;i++){
int x,y;
cin >> x >> y;
st[cnt].x = x,st[cnt].y = y;
cnt++;
}
sort(st,st + cnt,cmp1);
int ans = 0;
for(int j = 0;j < cnt - 1;j++){
if(st[j + 1].y == st[j].y && abs(st[j + 1].x - st[j].x) > 2){
ans++;
}
}
sort(st,st + cnt,cmp2);
for(int j = 0;j < cnt - 1;j++){
if(st[j + 1].x == st[j].x && abs(st[j + 1].y - st[j].y) > 2){
ans++;
}
}
cout << ans << "\n";
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
# B002 单词重组 (opens new window)
# 题目描述
在美国数以百万计的报纸中，有一种单词游戏称为猜词。游戏的目标是猜谜，为了找出答案中缺少的字母，有必要对4个单词的字母顺序重新调整。在本题中，你的任务是编写程序实现对单词中的字母顺序重新调整。
# 输入
输入文件包含4部分： （1） 一部字典，包含至少1个单词，至多100个单词，每个单词占一行；
（2） 字典后是一行字符串“XXXXXX”，表示字典结束；
（3） 一个或多个被打乱字母顺序的“单词”，每个单词占一行，你必须整理这些字母的顺序；
（4） 输入文件的最后一样为字符串“XXXXXX”，代表输入文件结束。
所有单词，包括字典中的单词和被打乱字母顺序的单词，都只包含小写英文字母，并且至少包含一个字母，至多包含6个字母。字典中的单词不一定是按顺序排列的，但保证字典中的单词是唯一的。
# 输出
对输入文件中每个被打乱字母顺序的单词w，按字母顺序输出字典中所有满足以下条件的单词的列表：通过调整单词w中的字母顺序，可以变成字典中的单词。列表中的每个单词占一行。如果列表为空（即单词w不能转换成字典中的任何一个单词），则输出一行字符串“NOT A VALID WORD”。以上两种情形都在列表后，输出一行包含6个星号字符的字符串，表示列表结束。
# 样例输入 复制
tarp given score refund only trap work earn course pepper part XXXXXX resco nfudre aptr sett oresuc XXXXXX# 样例输出 复制
score ****** refund ****** part tarp trap ****** NOT A VALID WORD ****** course ******
# 思路：
这道题笔者暂时只能想到这种做法，如果有更好的可以分享~
笔者这里是用map来实现的，就是给每个单词对应了一个排序后的映射，比如这里会认为abcd和dcba会有相同的映射即abcd。然后后续输出单词的时候，逐一输出map里相同映射的那些单词~
# 代码C++：
#include<bits/stdc++.h>
using namespace std;
map<string,string> mp;
int main(){
string s;
while(cin >> s){
if(s == "XXXXXX") break;
string str = s;
sort(s.begin(),s.end());
mp[str] = s;
}
while(cin >> s){
if(s == "XXXXXX") break;
int cnt = 0;
for (auto it = mp.begin(); it != mp.end(); ++it) {
// cout << it->first << " => " << it->second << '\n';
sort(s.begin(),s.end());
if(it -> second == s){
cnt++;
cout << it -> first << "\n";
}
}
if(cnt == 0){
cout << "NOT A VALID WORD\n******\n";
}else{
cout << "******\n";
}
}
}
# B003 英文姓名排序 (opens new window)
# 题目描述
在汉语里，对汉语姓名可以按拼音排序，也可以按笔画顺序排序。在英语里，对英语姓名主要按字母顺序排序。本题要求给定的一组英文姓名按长短顺序排序。
# 输入
输入文件中包含多个测试数据。每个测试数据的第1行是一个正整数N（0 < N < 100），表示该测试数据中英文姓名的数目；接下来有N行，每行为一个英文姓名，姓名中允许出现的字符有大小写英文字母、空格和点号（.），每个英文姓名长度至少为2、但不超过50.N=0表示输入结束。
# 输出
对输入文件中的每个测试数据，输出排序后的姓名。排序方法为：先按姓名长度从长到短的顺序排序，对长度相同的姓名，则按字母顺序排序。每2个测试数据的输出之间输出一个空行。
# 样例输入 复制
4 David A. Forsyth Jean Ponce Tom M. Mitchell Thomas H. Cormen 0# 样例输出 复制
David A. Forsyth Thomas H. Cormen Tom M. Mitchell Jean Ponce
# 思路：
这道题思路还是很简单的，就是排序，然后处理一下排序逻辑，但是因为阴间的一些换行符问题，这里不能用getchar()，所以用了getline去吞换行符。
# 代码C++：
#include<bits/stdc++.h>
using namespace std;
string str[1000];
bool cmp(string a,string b){
if(a.size() != b.size()) return a.size() > b.size();
return a < b;
}
int main(){
int n;
while(cin >> n){
if(!n) break;
string s;
getline(cin,s);
for(int i = 1;i <= n;i++){
getline(cin,s);
str[i] = s;
}
sort(str + 1,str + n + 1,cmp);
for(int i = 1;i <= n;i++){
cout << str[i] << "\n";
}
cout << "\n";
}
}
# B004 DNA排序 (opens new window)
# 题目描述
一个序列的逆序数定义为序列中无序元素对的数目。例如，在字符序列DAABEC中，逆序数为5，因为字符D比它右边的4个字符大，而字符E比它右边的1个字符大。字符序列AACEDGG只有1个逆序，即E和D,它几乎是已经排好序的，而字符序列“ZWQM”有6个逆序，它是最大程度的无序，即有序序列的逆序。 在本题中，你的任务是对DNA字符串（只包含字符“A”、“C”，“G”和“T”）进行排序。注意不是按照字母顺序，而是按照逆序数从低到高进行排序，所有字符串的长度都一样。
# 输入
输入文件中包含多组测试数据。每组测试数据的格式为：第1行为2个整数，正整数n(0 < n <= 50，表示字符串的长度)和正整数m(1 < m <= 100,表示字符串的数目)；然后是m行，每一行为一个字符串，长度为n。
# 输出
对应到输入文件中的N组测试数据，输出也有N组，每2组输出之间有一个空行。对每组输入数据，按逆序数从低到高输出各字符串，如果2个字符串的逆序数一行，则按输入时的先后顺序输出。
# 样例输入 复制
10 5 TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT# 样例输出 复制
CCCGGGGGGA GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA
# 思路：
笔者最开始还想着分两个数组进行处理，但是后面发现排序很难同步处理，干脆就换成结构体排序的写法了。
# 代码C++：
#include<bits/stdc++.h>
using namespace std;
struct node{
string s;
int cnt = 0;
}node[1000];
bool cmp(struct node a,struct node b){
return a.cnt < b.cnt;
}
int main(){
int n,m;
while(cin >> n >> m){
for(int i = 1;i <= m;i++){
string s;
cin >> s;
node[i].s = s;
int cnt = 0;
for(int j = 0;j < n;j++){
for(int k = j + 1;k < n;k++){
if(s[j] > s[k]) cnt++;
}
}
node[i].cnt = cnt;
}
sort(node + 1,node + m + 1,cmp);
for(int i = 1;i <= m;i++){
cout << node[i].s << "\n";
}
cout << "\n";
}
}
# B005 体重排序 (opens new window)
# 题目描述
作为一台很受欢迎的脱口秀节目的主持人，你正在做一期关于节食的节目。你的嘉宾是Kevorkian博士。他最近推出了一项减肥计划“Do You Want To Diet?”，这项计划向它的用户保证每天减肥1磅。 节目录制那天，你准备让一些使用Kevorkian博士减肥计划的节食者上台秀一下。你准备按他们的体重的递减顺序来安排他们出场的先后顺序。问题是他们报名时只提供了以下信息：姓名，节食的天数，节食前的体重。你要根据他们节食的天数来计算他们现在的体重。所有的节食者每天减肥1磅。
# 输入
输入文件包含至多100个测试数据。测试数据之间没有空行。每个测试数据包含3部分： 第1行为START； 接下来为节食者列表：包含1~10行，每行描述一名节食者，包括姓名、节食的天数和节食前的体重。其中姓名为1~20个数字、字母字符组成的字符串；节食的天数不超过1000天；节食前的体重不超过10,000。 最后一行为END。
# 输出
对每个测试数据，根据各节食者现在体重的递减顺序列出节食者的名字，每个节食者的名字占一行。每2个测试数据的输出之间有一个空行。
# 样例输入 复制
START Joe 10 110 END START James 100 150 Laura 100 140 Hershey 100 130 END# 样例输出 复制
Joe James Laura Hershey
# 思路：
这题主要是处理START和END有点麻烦，可以参考笔者这里的做法~
# 代码C++：
#include<bits/stdc++.h>
using namespace std;
struct node{
string name;
int day = 0;
int w = 0;
}node[10000];
bool cmp(struct node a,struct node b){
return a.w - a.day > b.w - b.day;
}
int main(){
string start;
string end;
while(cin >> start){
int cnt = 0;
string name;
int day = 0;
int w = 0;
while(cin >> name){
if(name == "END") break;
cin >> day >> w;
cnt++;
node[cnt].name = name;
node[cnt].day = day;
node[cnt].w = w;
}
sort(node + 1,node + cnt + 1,cmp);
for(int i = 1;i <= cnt;i++){
cout << node[i].name << "\n";
}
cout << "\n";
}
}
# B006 俄罗斯套娃 (opens new window)
# 题目描述
俄罗斯套娃大家应该都玩过。是一个按照大小顺序可以嵌套在一起的玩具。现在有一个被拆开的俄罗斯套娃摆到了你的好友面前，但是，要想把它重新变成一个娃娃，必须要满足这样的规则： 1.娃娃的大小必须是从小到大排列好的。 2.你每次只可以交换相邻的两个娃娃。 这样的规则使你的好友变得很烦躁，假设娃娃的个数为n，如果交换娃娃的次数超过n*(n - 1) / 2 - 1次，那么你的好友就会烧掉这些娃娃。但是她很珍惜这些娃娃。现在她向你询问，她是否不会烧掉这个俄罗斯套娃？
# 输入
一个整数n(n <= 1000) 接下来n个数Si，Si表示当前位置娃娃大小。（Si不一定小于n）。
# 输出
如果好友不会烧掉娃娃输出"YES"（没有引号），反之输出"NO"（没有引号）。
# 样例输入 复制
6 6 5 4 3 2 1# 样例输出 复制
NO
# 思路：
笔者最开始想得乱七八糟的，结果暴力排序就可以了hhh
# 代码C++：
#include<bits/stdc++.h>
using namespace std;
int s[1000];
int main(){
int n;
cin >> n;
for(int i = 0;i < n;i++){
cin >> s[i];
}
int cnt = 0;
for(int i = 0;i < n - 1;i++){
for(int j = 0;j < n - 1- i;j++){
if(s[j] > s[j + 1]){
int temp = s[j];
s[j] = s[j + 1];
s[j + 1] = temp;
cnt++;
}
}
}
cout << ((cnt > n * (n - 1) / 2 - 1) ? "NO\n" : "YES\n");
}
# B007 组合数字 (opens new window)
# 题目描述
现在给你n个正整数，a1，a2，a3........an，请你把它们首尾连接到一起，组成一个最小的正整数（可能会超出long long）。
# 输入
第一行有一个整数，表示数字个数 n。 第二行有 n 个整数，表示给出的 n 个整数 ai（1 <= n <= 20，1 <= ai <= 1e9）。
# 输出
一个正整数，表示最小的整数。
# 样例输入 复制
3 13 312 343# 样例输出 复制
13312343
# 思路：
很经典的字符串拼接比较的方法就是
bool cmp(string a,string b){ return a + b < b + a; }一定要理解哦~
# 代码C++：
#include<bits/stdc++.h>
using namespace std;
string a[1000];
bool cmp(string a,string b){
return a + b < b + a;
}
int main(){
int n;
cin >> n;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
sort(a + 1,a + n + 1,cmp);
for(int i = 1;i <= n;i++){
cout << a[i];
}
}