//因为是在vs2019上面写的，部分scanf写成了scanf_s。
A-前M大的数
还记得Gardon给小希布置的那个作业么？（上次比赛的1005）其实小希已经找回了原来的那张数表，现在她想确认一下她的答案是否正确，但是整个的答案是很庞大的表，小希只想让你把答案中最大的M个数告诉她就可以了。
给定一个包含N(N<=3000)个正整数的序列，每个数不超过5000，对它们两两相加得到的N*(N-1)/2个和，求出其中前M大的数(M<=1000)并按从大到小的顺序排列。
Input
输入可能包含多组数据，其中每组数据包括两行：
第一行两个数N和M，
第二行N个数，表示该序列。
请在这里输入引用内容
Output
对于输入的每组数据，输出M个数，表示结果。输出应当按照从大到小的顺序排列。
Sample Input
4 4
1 2 3 4
4 5
5 3 6 4
Sample Output
7 6 5 5
11 10 9 9 8
直接暴力求解，算出所有情况，再sort排序，依次输出。
#include<iostream>
#include<algorithm>
using namespace std;
int res[3013500];
int main()
{
int n, m, k;
int num[3005];
while (scanf("%d%d", &n, &m) != EOF) {
k = 0;
for (int i = 0; i < n; i++) {
cin >> num[i];
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
res[k] = num[i] + num[j];
k++;
}
}
sort(res, res + k);
for (int i = k - 1; i > k - m; i--) {
cout << res[i] << ' ';
}cout << res[k - m] << endl;
}
return 0;
}B - 稳定排序
大家都知道，快速排序是不稳定的排序方法。
如果对于数组中出现的任意a[i],aj,其中a[i]==a[j]，在进行排序以后a[i]一定出现在a[j]之前，则认为该排序是稳定的。
请在这里输入引用内容
某高校招生办得到一份成绩列表，上面记录了考生名字和考生成绩。并且对其使用了某排序算法按成绩进行递减排序。现在请你判断一下该排序算法是否正确，如果正确的话，则判断该排序算法是否为稳定的。
Input
本题目包含多组输入，请处理到文件结束。
对于每组数据，第一行有一个正整数N(0<N<300)，代表成绩列表中的考生数目。
接下来有N行，每一行有一个字符串代表考生名字(长度不超过50，仅包含'a'~'z'),和一个整数代表考生分数(小于500)。其中名字和成绩用一个空格隔开。
再接下来又有N行，是上述列表经过某排序算法以后生成的一个序列。格式同上。
Output
对于每组数据，如果算法是正确并且稳定的，就在一行里面输出"Right"。如果算法是正确的但不是稳定的，就在一行里面输出"Not Stable"，并且在下面输出正确稳定排序的列表，格式同输入。如果该算法是错误的，就在一行里面输出"Error",并且在下面输出正确稳定排序的列表，格式同输入。
请在这里输入引用内容
注意，本题目不考虑该排序算法是错误的，但结果是正确的这样的意外情况。
Sample Input
3
aa 10
bb 10
cc 20
cc 20
bb 10
aa 10
3
aa 10
bb 10
cc 20
cc 20
aa 10
bb 10
3
aa 10
bb 10
cc 20
aa 10
bb 10
cc 20
Sample Output
Not Stable
cc 20
aa 10
bb 10
Right
Error
cc 20
aa 10
bb 10
利用结构体，编写sort排序，排序后进行比较，分情况输出结果。
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
struct P
{
string name;
int num, l;
}p[300];
bool cmp1(P a, P b)
{
if (a.num == b.num)
return a.l < b.l;
else
return a.num > b.num;
}
int main() {
int n, k = 0;
int num[300];
char s[300][50];
while (scanf_s("%d",&n)!=EOF)
{
k = 0;
for (int i = 0; i < n; i++)
{
cin >> p[i].name >> p[i].num;
p[i].l = i;
}
/*stable_*/sort(p, p + n, cmp1);
for (int i = 0; i < n; i++)
{
cin >> s[i] >> num[i];
}
for (int i = 0; i < n; i++)
{
if (num[i] != p[i].num) {
k = 1; break;
}
else if (num[i] == p[i].num && s[i] != p[i].name) {
k = 2;
}
}
if (k == 0)
cout << "Right\n";
else {
if (k == 1)
cout << "Error\n";
else
cout << "Not Stable\n";
for (int i = 0; i < n; i++)
{
cout << p[i].name << ' ' << p[i].num << '\n';
}
}
}
return 0;
}C - 开门人和关门人
每天第一个到机房的人要把门打开，最后一个离开的人要把门关好。现有一堆杂乱的机房签
到、签离记录，请根据记录找出当天开门和关门的人。
Input
测试输入的第一行给出记录的总天数N ( > 0 )。下面列出了N天的记录。
每天的记录在第一行给出记录的条目数M ( > 0 )，下面是M行，每行的格式为
请在这里输入引用内容
证件号码 签到时间 签离时间
请在这里输入引用内容
其中时间按“小时:分钟:秒钟”（各占2位）给出，证件号码是长度不超过15的字符串。
Output
对每一天的记录输出1行，即当天开门和关门人的证件号码，中间用1空格分隔。
注意：在裁判的标准测试输入中，所有记录保证完整，每个人的签到时间在签离时间之前，
且没有多人同时签到或者签离的情况。
Sample Input
3
1
ME3021112225321 00:00:00 23:59:59
2
EE301218 08:05:35 20:56:35
MA301134 12:35:45 21:40:42
3
CS301111 15:30:28 17:00:10
SC3021234 08:00:00 11:25:25
CS301133 21:45:00 21:58:40
Sample Output
ME3021112225321 ME3021112225321
EE301218 MA301134
SC3021234 CS301133
本题将编号，进入时间和出去的时间全部写成字符串，然后编写排序函数，使用sort排序，然后输出结果。
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
struct P
{
string num, come, go;
}p[1000];
bool cmpr(P a, P b) {
return a.come > b.come;
}
bool cmpc(P a, P b) {
return a.go > b.go;
}
int main() {
int n, m;
char c,r;
cin >> n;
for (int i = 0; i < n; i++){
cin >> m;
for (int j = 0; j < m; j++){
cin >> p[j].num >> p[j].come >> p[j].go;
}
sort(p, p + m, cmpr);
cout << p[m - 1].num << ' ';
sort(p, p + m, cmpc);
cout << p[0].num << '\n';
}
return 0;
}D - EXCEL排序
Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。
Input
测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (<=100000) 和 C，其中 N 是纪录的条数，C 是指定排序的列号。以下有 N
行，每行包含一条学生纪录。每条学生纪录由学号（6位数字，同组测试中没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（闭区间[0, 100]内的整数）组成，每个项目间用1个空格隔开。当读到 N=0 时，全部输入结束，相应的结果不要输出。
Output
对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3
时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。
Sample Input
3 1
000007 James 85
000010 Amy 90
000001 Zoe 60
4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98
4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90
0 0
Sample Output
Case 1:
000001 Zoe 60
000007 James 85
000010 Amy 90
Case 2:
000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60
Case 3:
000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90
本题同C题，编写排序函数并sort排序，输出结果。
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
struct P {
string num, name;
int gra;
}p[100005];
bool cmp1(P a, P b) {
return a.num < b.num;
}
bool cmp2(P a, P b) {
if(a.name!=b.name)
return a.name < b.name;
else
return a.num < b.num;
}
bool cmp3(P a, P b) {
if (a.gra != b.gra)
return a.gra < b.gra;
else
return a.num < b.num;
}
int main() {
int n, m, c=1;
while (scanf_s("%d %d", &n, &m) != EOF) {
if (n == 0)
break;
for (int i = 0; i < n; i++){
cin >> p[i].num >> p[i].name >> p[i].gra;
}
if (m == 1)
stable_sort(p, p + n, cmp1);
if (m == 2)
stable_sort(p, p + n, cmp2);
if (m == 3)
stable_sort(p, p + n, cmp3);
printf("Case %d:\n", c++);
for (int i = 0; i < n; i++)
{
cout << p[i].num <<' ' << p[i].name << ' '<< p[i].gra << '\n';
}
}
}E - {A} + {B}
给你两个集合，要求{A} + {B}.
注:同一个集合中不会有两个相同的元素.
Input
每组输入数据分为三行,第一行有两个数字n,m(0<n,m<=10000),分别表示集合A和集合B的元素个数.后两行分别表示集合A和集合B.每个元素为不超出int范围的整数,每个元素之间有一个空格隔开.
Output
针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,每个元素之间有一个空格隔开.
Sample Input
1 2
1
2 3
1 2
1
1 2
Sample Output
1 2 3
1 2
本题使用set进行去重和排序，然后依次输出。
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main() {
int n, m;
while (scanf_s("%d%d", &n, &m) != EOF) {
set<int> x;
for (int i = 0; i < n; i++)
{
int j;
cin >> j;
x.insert(j);
}
for (int i = 0; i < m; i++)
{
int j;
cin >> j;
x.insert(j);
}
cout << *x.begin();
x.erase(x.begin());
while (!x.empty())
{
printf(" %d", *x.begin());
x.erase(x.begin());
}cout << '\n';
}
return 0;
}F - 水果
夏天来了
好开心啊,呵呵,好多好多水果
Joe经营着一个不大的水果店.他认为生存之道就是经营最受顾客欢迎的水果.现在他想要一份水果销售情况的明细表,这样Joe就可以很容易掌握所有水果的销售情况了.
Input
第一行正整数N(0<N<=10)表示有N组测试数据.
每组测试数据的第一行是一个整数M(0<M<=100),表示工有M次成功的交易.其后有M行数据,每行表示一次交易,由水果名称(小写字母组成,长度不超过80),水果产地(小写字母组成,长度不超过80)和交易的水果数目(正整数,不超过100)组成.
Output
对于每一组测试数据,请你输出一份排版格式正确(请分析样本输出)的水果销售情况明细表.这份明细表包括所有水果的产地,名称和销售数目的信息.水果先按产地分类,产地按字母顺序排列;同一产地的水果按照名称排序,名称按字母顺序排序.
两组测试数据之间有一个空行.最后一组测试数据之后没有空行.
Sample Input
1
5
apple shandong 3
pineapple guangdong 1
sugarcane guangdong 1
pineapple guangdong 3
pineapple guangdong 1
Sample Output
guangdong
|----pineapple(5)
|----sugarcane(1)
shandong
|----apple(3)
本题使用map，然后排序，依次输出。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
struct P
{
string s, t;
int num;
}p[100];
bool cmp1(P a, P b) {
if (a.t != b.t)
return a.t < b.t;
else
return a.s < b.s;
}
int main() {
int n, m, all = 0, js;
string cd,cs;
cin >> n;
for (int j = 0; j < n; j++){
cin >> m;
for (int i = 0; i < m; i++){
cin >> p[i].s >> p[i].t >> p[i].num;
}
all = 0;
p[m].s = "-"; p[m].s = "-"; p[m].num = -1;
sort(p, p + m, cmp1);
cd = p[0].t; cs = p[0].s;
cout << cd << '\n';
for (int i = 0; i <= m; i++){
if (p[i].s == cs) {
all+= p[i].num;
}
else {
cout << " |----" << cs << '(' << all << ')';
all = p[i].num;
cs = p[i].s;
if (j != n - 1)
if(i!=m)
cout << '\n';
if (j == n - 1 && p[i].num != -1)
cout << '\n';
}
if (p[i].t != cd) {
cd = p[i].t;
cout << cd << '\n';
}
}if (j != n - 1)
cout << '\n';
}
return 0;
}G - 不重复数字
给出N个数，要求把其中重复的去掉，只保留第一次出现的数。
例如，给出的数为1 2 18 3 3 19 2 3 6 5 4，其中2和3有重复，去除后的结果为1 2 18 3 19 6 5 4。Input
输入第一行为正整数T，表示有T组数据。
接下来每组数据包括两行，第一行为正整数N，表示有N个数。第二行为要去重的N个正整数。Output
对于每组数据，输出一行，为去重后剩下的数字，数字之间用一个空格隔开。
Sample Input
2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6
Sample Output
1 2 18 3 19 6 5 4
1 2 3 4 5 6
Hint
对于30%的数据，1 <= N <= 100，给出的数不大于100，均为非负整数；
对于50%的数据，1 <= N <= 10000，给出的数不大于10000，均为非负整数；
对于100%的数据，1 <= N <= 50000，给出的数在32位有符号整数范围内。
提示:
由于数据量很大，使用C++的同学请使用scanf和printf来进行输入输出操作，以免浪费不必要的时间。
本题同上题，使用map进行解题。
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
int n, t, x;
map<int, int> p;
int main() {
cin >> t;
while (t--) {
bool res = false;
p.clear();
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
if (!p[x]) {
p[x] = 1;
if (!res) {
res = true;
cout << x;
}
else
cout << ' ' << x;
}
}
cout << '\n';
}
}H - 表达式括号匹配
给出一个表达式，该表达式仅由字符(、)、+、-以及数字组成。
请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回"YES"；否则返回"NO"。
输入格式
一行一个表达式，长度不超过
2000
。若匹配，则输出"YES"；否则输出"NO"
Sample Input
2+(3-4)-2-6)
Sample Output
NO
本题直接通过判断'('和')'的数量进行判断即可。
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
int n, t, x;
map<int, int> p;
int main() {
cin >> t;
while (t--) {
bool res = false;
p.clear();
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
if (!p[x]) {
p[x] = 1;
if (!res) {
res = true;
cout << x;
}
else
cout << ' ' << x;
}
}
cout << '\n';
}
}
京公网安备 11010502036488号