在线可以做翻译的网站吗,山西网站制作设计,网站 微信 app,国外有没有做问卷调查的网站A. DS排序--简单选择排序
题目描述
给出一个数据序列#xff0c;使用简单选择排序算法进行升序排序。
输入
第一行输入t#xff0c;表示有t个测试示例 第二行输入n#xff0c;表示第一个示例有n个数据(n1) 第三行输入n个数据#xff0c;都是正整数#xff0c;数据…A. DS排序--简单选择排序
题目描述
给出一个数据序列使用简单选择排序算法进行升序排序。
输入
第一行输入t表示有t个测试示例 第二行输入n表示第一个示例有n个数据(n1) 第三行输入n个数据都是正整数数据之间用空格隔开 以此类推
输出
对每组测试数据输出每趟排序结果。不同组测试数据间用空行分隔。
样例查看模式
正常显示查看格式
输入样例1
2\n 5\n 12 58 36 47 96\n 10\n 1 3 6 9 0 8 5 7 4 2\n
输出样例1
12 58 36 47 96\n 12 36 58 47 96\n 12 36 47 58 96\n 12 36 47 58 96\n \n 0 3 6 9 1 8 5 7 4 2\n 0 1 6 9 3 8 5 7 4 2\n 0 1 2 9 3 8 5 7 4 6\n 0 1 2 3 9 8 5 7 4 6\n 0 1 2 3 4 8 5 7 9 6\n 0 1 2 3 4 5 8 7 9 6\n 0 1 2 3 4 5 6 7 9 8\n 0 1 2 3 4 5 6 7 9 8\n 0 1 2 3 4 5 6 7 8 9\n \n
AC代码
#includeiostream
#includevector
using namespace std;
void display(vectorintv)
{int n v.size();for (int i 0; i n - 1; i){cout v[i] ;}cout v[n - 1] endl;
}
void select(vectorintv)
{int nv.size();for(int i0;in-1;i){int tempv[i];int idxj0;bool flag0;for(int ji1;jn;j){if(v[j]temp){tempv[j];idxjj;flag1;}}if(flag)swap(v[i],v[idxj]);display(v);}
}
int main()
{int t;cin t;while (t--){int n;cin n;vectorinta;for (int i 0; i n; i){int x;cin x;a.push_back(x);}select(a);cout endl;}return 0;
}
B. DS内排—堆排序
题目描述
给定一组数据使用堆排序完成数据的降序排序。建小顶堆)。
输入
数据个数nn个整数数据
输出
初始创建的小顶堆序列
每趟交换、筛选后的数据序列输出格式见样例
样例查看模式
正常显示查看格式
输入样例1
8 34 23 677 2 1 453 3 7\n \n
输出样例1
8 1 2 3 7 23 453 677 34\n 8 2 7 3 34 23 453 677 1\n 8 3 7 453 34 23 677 2 1\n 8 7 23 453 34 677 3 2 1\n 8 23 34 453 677 7 3 2 1\n 8 34 677 453 23 7 3 2 1\n 8 453 677 34 23 7 3 2 1\n 8 677 453 34 23 7 3 2 1
AC代码
#includeiostream
#includevector
using namespace std;
int n;
vectorinta;
void min_heap(int st, int ed)
{int p st;int son st * 2 1;while (son ed){if (son 1 ed a[son] a[son 1]){son;}if (a[p] a[son])return;swap(a[p], a[son]);p son;son 2 * p 1;}
}
void heap_sort()
{for (int i n / 2 - 1; i 0; i--){min_heap(i, n - 1);}cout n;for (int i 0; i n; i){cout a[i];}cout endl;for (int i n - 1; i 0; i--){swap(a[0], a[i]);min_heap(0,i - 1);cout n;for (int i 0; i n; i){cout a[i];}cout endl;}
}
int main()
{cin n;for (int i 0; i n; i){int x;cin x;a.push_back(x);}heap_sort();return 0;
}
C. DS内排—2-路归并排序
题目描述
输入一组字符串用2-路归并排序按字典顺序进行降序排序。
输入
测试次数t
每组测试数据数据个数n后跟n个字符串字符串不含空格。
输出
对每组测试数据输出2-路归并排序的每一趟排序结果。每组测试数据的输出之间有1空行。
样例查看模式
正常显示查看格式
输入样例1
2\n 6 shenzhen beijing guangzhou futian nanshan baoan\n 10 apple pear peach grape cherry dew fig haw lemon marc\n \n \n
输出样例1
shenzhen beijing guangzhou futian nanshan baoan\n shenzhen guangzhou futian beijing nanshan baoan\n shenzhen nanshan guangzhou futian beijing baoan\n \n pear apple peach grape dew cherry haw fig marc lemon\n pear peach grape apple haw fig dew cherry marc lemon\n pear peach haw grape fig dew cherry apple marc lemon\n pear peach marc lemon haw grape fig dew cherry apple
AC代码
#includeiostream
#includevector
using namespace std;
void print(vectorstringk)
{for (int i 1; i k.size() - 1; i){cout k[i] ;}cout k[k.size() - 1] endl;
}
void merge(vectorstring k, vectorstring d,int l,int m,int r)
{int i l, j m 1, kk l;while (i m j r){if (k[i] k[j])d[kk] k[i];//降序else d[kk] k[j];}while (i m)d[kk] k[i];while (j r)d[kk] k[j];
}
void merge_sort(vectorstring k, vectorstring d)
{int len k.size() - 1;int l, m, r, i;for (i 1; i len; i * 2)//区间长度{for (l 1; l len; l 2 * i)//区间起始点{m l i - 1;if (m len)break;r l 2 * i - 1;if (r len)r len;merge(k, d, l, m, r);}for (int t 1; t len; t)k[t] d[t];print(k);}
}
int main()
{int t;cin t;while (t--){int n;cin n;vectorstringkey(n 1);vectorstringdata(n 1);for (int i 1; i n; i){cin key[i];}merge_sort(key, data);cout endl;}return 0;
}
D. 奥运排行榜
题目描述
每年奥运会各大媒体都会公布一个排行榜但是细心的读者发现不同国家的排行榜略有不同。比如中国金牌总数列第一的时候中国媒体就公布“金牌榜”而美国的奖牌总数第一于是美国媒体就公布“奖牌榜”。如果人口少的国家公布一个“国民人均奖牌榜”说不定非洲的国家会成为榜魁…… 现在就请你写一个程序对每个前来咨询的国家按照对其最有利的方式计算它的排名。
输入
输入的第一行给出两个正整数N和M≤224因为世界上共有224个国家和地区分别是参与排名的国家和地区的总个数、以及前来咨询的国家的个数。为简单起见我们把国家从0 ~ N−1编号。之后有N行输入第i行给出编号为i−1的国家的金牌数、奖牌数、国民人口数单位为百万数字均为[0,1000]区间内的整数用空格分隔。最后面一行给出M个前来咨询的国家的编号用空格分隔。
输出
在一行里顺序输出前来咨询的国家的排名:计算方式编号。其排名按照对该国家最有利的方式计算计算方式编号为金牌榜1奖牌榜2国民人均金牌榜3国民人均奖牌榜4。输出间以空格分隔输出结尾不能有多余空格。
若某国在不同排名方式下有相同名次则输出编号最小的计算方式。
样例查看模式
正常显示查看格式
输入样例1
4 4\n 51 100 1000\n 36 110 300\n 6 14 32\n 5 18 40\n 0 1 2 3
输出样例1
1:1 1:2 1:3 1:4
AC代码
#includeiostream
#includevector
#includealgorithm
using namespace std;
struct country
{int num;int gold;int medal;int people;
};
int n, m;
vectorcountryc;
vectorpairint, intgg;
vectorpairint, intmm;
vectorpairdouble, intagg;
vectorpairdouble, intamm;
int main()
{cin n m;for (int i 0; i n; i){int x, y, z;cin x y z;c.push_back({ i,x,y,z });gg.push_back({ x,i });mm.push_back({ y,i });agg.push_back({ (1.0 * x) / z,i });amm.push_back({ (1.0 * y) / z,i });}sort(gg.rbegin(), gg.rend());sort(mm.rbegin(), mm.rend());sort(agg.rbegin(), agg.rend());sort(amm.rbegin(), amm.rend());for (int i 0; i m; i){int x;cin x;int paiming n;int idx 0;for (int j 0; j n; j){if (amm[j].second x){if (paiming j 1){paiming j 1;idx 4;break;}}}for (int j 0; j n; j){if (agg[j].second x){if (paiming j 1){paiming j 1;idx 3;break;}}}for (int j 0; j n; j){if (mm[j].second x){if (paiming j 1){paiming j 1;idx 2;break;}}}for (int j 0; j n; j){if (gg[j].second x){if (paiming j1){paiming j1;idx 1;break;}}}cout paiming : idx;if (i ! m - 1)cout ;else cout endl;}return 0;
}
E. 关于堆的判断
题目描述
将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种
x is the rootx是根结点x and y are siblingsx和y是兄弟结点x is the parent of yx是y的父结点x is a child of yx是y的一个子结点。
输入
每组测试第1行包含2个正整数N≤ 1000和M≤ 20分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[−10000,10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行每行给出一个命题。题目保证命题中的结点键值都是存在的。
输出
对输入的每个命题如果其为真则在一行中输出T否则输出F。
样例查看模式
正常显示查看格式
输入样例1
5 4\n 46 23 26 24 10\n 24 is the root\n 26 and 23 are siblings\n 46 is the parent of 23\n 23 is a child of 10
输出样例1
F\n T\n F\n T
AC代码
#includeiostream
#includevector
#includealgorithm
#includequeue
#includemap
#includestring
using namespace std;
const int N 1e5 10;
int n, m;
mapint, intmp;
int h[N];
int cnt;
void up(int u)
{while (u / 2 h[u] h[u / 2]){swap(h[u], h[u / 2]);u / 2;}
}
int main()
{cin n m;for (int i 1; i n; i){int x;cin x;h[cnt] x;up(i);}getchar();for (int i 1; i n; i)mp[h[i]] i;for (int i 0; i m; i){string s;getline(cin, s);vectorstringtt;string temp;for (int i 0; i s.size(); i){if (s[i] ! )temp s[i];else{tt.push_back(temp);temp.clear();}}tt.push_back(temp);int nn tt.size();int num1 stoi(tt[0]);int num2 0;if (tt[nn - 1] root){if (mp[num1] 1){cout T endl;}else cout F endl;continue;}if (tt[nn - 1] siblings){num2 stoi(tt[2]);if (mp[num1]/2 mp[num2]/2){cout T endl;}else cout F endl;continue;}if (tt[3] parent){num2 stoi(tt[nn - 1]);if (mp[num1] mp[num2]/2){cout T endl;}else cout F endl;continue;}if (tt[3] child){num2 stoi(tt[nn - 1]);if (mp[num1]/2 mp[num2]){cout T endl;}else cout F endl;continue;}}return 0;
}
F. 插入排序还是归并排序
题目描述
根据维基百科的定义
插入排序是迭代算法逐一获得输入数据逐步产生有序的输出序列。每步迭代中算法从输入序列中取出一元素将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作首先将原始序列看成 N 个只包含 1 个元素的有序子序列然后每次迭代归并两个相邻的有序子序列直到最后只剩下 1 个有序的序列。
现给定原始序列和由某排序算法产生的中间序列请你判断该算法究竟是哪种排序算法
输入
输入在第一行给出正整数 N (≤100)随后一行给出原始序列的 N 个整数最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔且行首尾不得有多余空格。
样例查看模式
正常显示查看格式
输入样例1
10\n 3 1 2 8 7 5 9 4 6 0\n 1 2 3 7 8 5 9 4 6 0
输出样例1
Insertion Sort\n 1 2 3 5 7 8 9 4 6 0
AC代码
#includeiostream
#includevector
#includealgorithm
#includequeue
#includemap
#includestring
using namespace std;
vectorintcheck;
vectorvectorintmm;
vectorvectorintii;
void print(vectorintk)
{for (int i 1; i k.size() - 1; i){cout k[i] ;}cout k[k.size() - 1] endl;
}
void merge(vectorint k, vectorint d, int l, int m, int r)
{int i l, j m 1, kk l;while (i m j r){if (k[i] k[j])d[kk] k[i];else d[kk] k[j];}while (i m)d[kk] k[i];while (j r)d[kk] k[j];
}
void merge_sort(vectorint k, vectorint d)
{int len k.size() - 1;int l, m, r, i;for (i 1; i len; i * 2)//区间长度{vectorintkk;for (l 1; l len; l 2 * i)//区间起始点{m l i - 1;if (m len)break;r l 2 * i - 1;if (r len)r len;merge(k, d, l, m, r);}for (int t 1; t len; t)k[t] d[t];for (int t 1; t len; t){kk.push_back(k[t]);}mm.push_back(kk);}
}
void insert_sort(vectorint a)
{int n a.size()-1;for (int i 2; i n; i){int j;int tt a[i];vectorintkk;for (j i - 1; j 1; j--){if (a[j] tt){a[j 1] a[j];}else break;}a[j 1] tt;for (int i 1; i n; i){kk.push_back(a[i]);}ii.push_back(kk);}
}
int main()
{int nn;cin nn;vectorintk1(nn 1);vectorintmk1(nn 1);vectorintk2(nn1);for (int i 1; i nn; i){cin k1[i];k2[i] k1[i];}for (int i 0; i nn; i){int x;cinx;check.push_back(x);}insert_sort(k2);merge_sort(k1, mk1);bool ok 0;for (int i 0; i mm.size(); i){if (check mm[i]){ok 1;cout Merge Sort endl;for (int j 0; j mm[i 1].size(); j){if (j 0)cout mm[i 1][j];else cout mm[i 1][j];}break;}}if (!ok){for (int i 0; i ii.size(); i){if (check ii[i]){cout Insertion Sort endl;for (int j 0; j ii[i 1].size(); j){if (j 0)cout ii[i 1][j];else cout ii[i 1][j];}break;}}}return 0;
}
