算法考核题目总结

98 阅读 0 评论 65 点赞

我是靠谱客的博主勤劳吐司，最近开发中收集的这篇文章主要介绍算法考核题目总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A-快乐排排排

老师最近对学生成绩的排列特别头疼，你来帮帮他吧！
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函数的回顾


return strcmp(a.xuhao ,b.xuhao )<0;
}
bool namecmp(student a,student b)
{
if(strcmp(a.name,b.name )==0)
return strcmp(a.xuhao ,b.xuhao )<0;
else
return strcmp(a.name ,b.name )<0;
}
bool scorecmp(student a,student b)
{
if(a.score ==b.score )
return strcmp(a.xuhao ,b.xuhao )<0;
else
return a.score <b.score ;
}
int main()
{
int n,c,i,f=0;
while(1)
{
scanf("%d %d",&n,&c);
if(n==0)
return 0;
else
{
f++;
for(i=0;i<n;i++)
{
scanf("%s %s %d",&p[i].xuhao ,&p[i].name ,&p[i].score);
}
switch(c)
{
case 1:{
sort(p,p+n,xuhaocmp);
break;
}
case 2:	{
sort(p,p+n,namecmp);
break;
}
case 3:{
sort(p,p+n,scorecmp);
break;
}
}
printf("Case %d:n",f);
for(i=0;i<n;i++)
{
printf("%s %s %dn",p[i].xuhao ,p[i].name ,p[i].score);
}
}
}
}

B - 今天星期几？

今天瑶瑶想要去找女友约会，于是他中午吃过饭就跑去和妈妈说要去女友家，瑶瑶妈妈说作业写完了再去，但是瑶瑶不想写作业。于是，瑶瑶一直缠着妈妈，最后瑶瑶妈要给瑶瑶出一个问题，如果瑶瑶答对了，就让瑶瑶出去玩。已知，今天是2021年1月1号Friday，给你一个日期，说说那天是星期几？
瑶瑶一听简直快要崩溃，为了瑶瑶能出去找女友，全靠你了！！！

Input
多实例，每一组实例占一行，包括三个整数，分别是 year(0<year<=10000), month(0<=month<13), day(0<=day<32).

Output
输出有一行，如果数据是不合规则的，请输出"illegal"，否则请输出那一天是星期几。

Sample Input
2021 1 1

Sample Output
Friday

Hint
星期一，星期二，星期三，星期四，星期五，星期六，星期日，
分别是：Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday
注意输入数据不合规则的情况！
本题收获：
二维数组的使用、闰年的判断


```c
#include<stdio.h>
int panduan(int year);
int panduan(int year)
{
if(year%400==0||(year%4==0&&year%100!=0))
return 1;
return 0;
}
int main()
{
int i,year,month,day;
int t[2][31]= {{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};
while(scanf("%d %d %d",&year,&month,&day)!=EOF)
{
if(panduan(year)==0&&month==2&&day>28||year==0||month==0||day==0||day>t[panduan(year)][month]||month>12)
{
printf("illegaln");
}
else
{
for(i=1; i<year; i++)
day+=365+panduan(i);
for(i=1; i<month; i++)
day+=t[panduan(year)][i];
day%=7;
if(day==0)
printf("Sundayn");
else if(day == 1)
printf("Mondayn");
else if(day == 2)
printf("Tuesdayn");
else if(day == 3)
printf("Wednesdayn");
else if(day == 4)
printf("Thursdayn");
else if(day == 5)
printf("Fridayn");
else if(day == 6)
printf("Saturdayn");
}
}
return 0;
}

C - 我要算算算！

后缀表达式是一种把运算符后置的算术表达式，例如普通的表达式2 + 3的后缀表示法为2 3 +。后缀表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的后缀表示法为 2 3 + 4 *。本题求解后缀表达式的值，其中运算符包括+ - * /四个。
计算后缀表达式，要从前向后遍历字符串。当遇见运算数时，压入栈中。当读到运算符时，将栈中的连续2个运算数弹栈用当前运算符计算后（注意后缀表达式的先出栈的运算数，放在运算符后面；后出栈的运算数，放在运算符前面），再将结果压栈。最后的栈顶就是前缀表达式的运算结果。

Input
输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。

Output
输出为一行，表达式的值。可使用以下语句保留固定长度的小数点后尾数
C++：cout<<setiosflags(ios::fixed)<<setprecision(6)<<ans<<endl;
C：printf("%.6lfn", ans);

Sample Input
11.0 12.0 + 24.0 35.0 + *

Sample Output
1357.000000

Hint
double atof( char * ) ;
该函数的作用是将字符串转换为double型，在math.h中
本题收获：
栈的简单使用、atof函数使用

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <stack>
#include<cstring>
#include <iomanip>
using namespace std;
int main(){
stack<double> S;
double a,b,x;
char ch[100];
while(scanf("%s",ch)!=EOF){
int len=strlen(ch);
if(len==1){
if(ch[0] == '+'){
a=S.top();S.pop();
b=S.top();S.pop();
S.push(a+b);
}
else if(ch[0] == '-'){
a=S.top();S.pop();
b=S.top();S.pop();
S.push(b-a);
}
else if(ch[0] == '*'){
a=S.top();S.pop();
b=S.top();S.pop();
S.push(a*b);
}
else if(ch[0] == '/'){
a=S.top();S.pop();
b=S.top();S.pop();
S.push(b/a);
}
else if(ch[0]=='-'&&(ch[1]>='0'||ch[1]<='9')){
a=atof(ch);
a=-a;
S.push(a);
}else{
a=atof(ch);
S.push(a);
}
}else{
a=atof(ch);
S.push(a);
}
}
printf("%.6lfn",S.top());
return 0;
}

D - 想吃KFC吗？

伊菲的家在乡下，而梅基的家在市中心。于是，伊菲和梅基安排在KFC见面。西安有很多KFC，他们想选择一个花费总时间最短的KFC见面。
现在给你一张西安的地图，伊菲和梅基都可以上、下、左、右移动到相邻的地点，每移动一个位置花费11分钟。

Input
输入包含多个测试用例。
每个测试用例包括前两个整数n，m.（2<=n，m<=200）。
接下来的n行，每行包含m个字符。
“Y”表示伊菲的初始位置。
“M”表示梅基初始位置。
“#”死路；
'.'可走的路。
“@” KCF

Output
对于每个测试用例，输出伊菲和梅基花费的最短总时间。总有一家KFC可以让他们见面。

Sample Input
4 4
Y.#@
….
.#…
@…M
4 4
Y.#@
….
.#…
@#.M
5 5
Y…@.
.#…
.#…
@…M.
#…#

Sample Output
66
88
66
本题收获：
bfs、栈使用

//考核第四题总结 
#include <stdio.h>//旧式c++头文件风格，其实也可改成cstdio 
#include <string.h>//旧式 
#include <queue>
#include <algorithm>
#define inf 0x6ffffff//无穷大，也可以是0x3f3f3f3f 
using namespace std;
char map [202][202];
int vis
[202][202];
int flag1[202][202];
//由于要遍历两次 
int flag [202][202];
int n,m;
int x1,y1,x2,y2;//初始位置坐标 
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct node//注意c++定义结构体方法 
{
int x,y,step;
};
bool check(int x,int y)//检查是否越界 
{
if(x < 0 ||y < 0 ||x >= n ||y >= m ||map[x][y] == '#' ||vis[x][y]) //检查是否越界，是否已经搜过
return 0;
return 1;
}
void bfs(int x,int y,int a[][202])
{
int i;
node st,ed;
queue<node>q;//申请结构体队列 
st.x = x;//初始化 
st.y = y;
st.step = 0;
q.push(st);
while(!q.empty())
{
st = q.front();
q.pop();
for(i = 0;i < 4;i ++)
{
ed.x = st.x + dir[i][0];
ed.y = st.y + dir[i][1];
//其实这可以换成两个数组 
//比如
//我们一开始定义int a[4]={1,-1,0,0},int b[4]={0,0,1,-1} 
//那上面遍历更新新坐标就可以写成
//ed.x=st.x+a[i];ed.y=st.y+b[i];
if(!check(ed.x,ed.y))
continue;
ed.step = st.step+1;
vis[ed.x][ed.y] = 1;
if(map[ed.x][ed.y] == '@')
{
a[ed.x][ed.y] = ed.step;
}
q.push(ed);
}
}
}
int main()
{
int i,j;
while(~scanf("%d%d",&n,&m))
{
memset(flag,0,sizeof(flag));//初始化，注意格式memset(变量名，初始化值，变量类型的尺寸) 
memset(vis,0,sizeof(vis));
memset(flag1,0,sizeof(flag1));
for(i = 0;i < n;i ++)
scanf("%s",map[i]);//还可以这样向二维数组中录入字符
for(i = 0;i < n;i ++)
for(j = 0;j < m;j ++){
if(map[i][j] == 'Y'){//一开始的思路是录入的时候标记，其实不用，可以之后遍历
x1 = i;
y1 = j;
}
if(map[i][j] == 'M'){//可以两个坐标一起找
x2 = i;
y2 = j;
}
}
vis[x1][y1] = 1;
bfs(x1,y1,flag);
memset(vis,0,sizeof(vis));
vis[x2][y2] = 1;
bfs(x2,y2,flag1);
int min = inf;
for(i = 0;i < n;i ++)
for(j = 0;j < m;j ++)
{
if(min > flag[i][j] + flag1[i][j] && flag[i][j] && flag1[i][j])//有值的地方说明有KFC，找出两个人同时到达一个KFC的最短时间
min = flag[i][j] + flag1[i][j];
}
printf("%dn",min*11);
}
}

留有疑问？？？

E - 我不想复习！

明天，Peter 有一次生物考试。他不太喜欢这门课，但在 d 天以前，他得知自己必须参加这次考试。Peter 的父母很严格，要求他立即为此次考试而准备，为此他必须每第 i 天学习不少于 minTimei 小时且不多于 maxTimei 小时。除此之外，他们还警告 Peter，将会在考试的前一天检查他是否遵循了他们的指令。

因此，今天就是 Peter 的父母要求他出示考前复习准备时间表的日子。但是，这个男孩只记录了复习准备所花的累计小时数 sumTime ，现在他想知道能否给他的父母展示一份包含了 d 个数字的 sсhedule ，其中每个数字 sсhedulei 表示 Peter 每第 i 天所花在生物学习上的小时数，且满足他的父母所要求的约束条件，同时所有 schedulei 的总和应当等于 sumTime 。

输入
输入的第一行包含了两个整数 d, sumTime (1 ≤ d ≤ 30, 0 ≤ sumTime ≤ 240) — Peter 用于学习的天数，以及花在复习准备上的小时数总和。接下来的 d 行中，每一行包含两个以空格分隔的整数 minTimei, maxTimei (0 ≤ minTimei ≤ maxTimei ≤ 8) — Peter 可以在第 i 天花费的最少小时数，以及最多小时数。

输出
如果 Peter 遵循了他的父母的指令，则在第一行中打印 YES ，并在第二行中打印以空格分隔的 d 个数字，每个数字表示 Peter 在相应的日子中复习准备所花的小时数；否则，在唯一的一行中打印 NO 。如果有多个答案，则打印他们中的任意一种。

示例
输入
1 48
5 7
输出
NO
输入
2 5
0 1
3 5
输出
YES
1 4
本题收获：贪心算法复习

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int d, sumtime;
struct node{
int s, e, index;
}day[50];
void print()
{
for(int i = 0; i < d - 1; i++)
printf("%d ", day[i].s);
printf("%dn", day[d-1].s);
return ;
}
int main()
{
while(scanf("%d%d", &d, &sumtime) != EOF){
int sums = 0;
int sume = 0;
for(int i = 0; i < d; i++){
scanf("%d%d", &day[i].s, &day[i].e);
day[i].index = i + 1;
sums += day[i].s;
sume += day[i].e;
}
int flag = 0;
if(sums <= sumtime && sume >= sumtime){
printf("YESn");
flag = 1;
}
else if(sumtime < sums || sumtime > sume){
printf("NOn");
continue;
}
int flag1 = 0;
if(flag){
if(sums == sumtime){
print();
flag1 = 1;
}
if(flag1)
continue;
if(sume == sumtime){
for(int i = 0; i < d; i++)
day[i].s = day[i].e;
print();
flag1 = 1;
}
if(flag1)
continue;
if(sums < sumtime && sume > sumtime){
for(int i = 0; i < d; i++){
if(day[i].s == day[i].e)
continue;
for(int j = day[i].s; j < day[i].e;){
sums -= day[i].s;
j = j + 1;
sums += j;
day[i].s = j;
if(sums == sumtime)
print();
}
}
}
}
}
}