春招笔试题

拍卖

题目描述

公司最近新研发了一种产品,共生产了n件。有m个客户想购买此产品,第i个客户出价Vi元。为了确保公平,公司决定要以一个固定的价格出售产品。每一个出价不低于要价的客户将会得到产品,余下的将会被拒绝购买。请你找出能让公司利润最大化的售价。

输入

输入第一行二个整数n(1<=n<=1000),m(1<=m<=1000),分别表示产品数和客户数。
接下来第二行m个整数Vi(1<=Vi<=1000000),分别表示第i个客户的出价。

输出

输出一行一个整数,代表能够让公司利润最大化的售价。

样例输入

5 4
2 8 10 7

样例输出

7

分析与代码

排序,扫描所有情况,取出最大的就好了,代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
str=raw_input().split()
n=int(str[0])
m=int(str[1])
v=[]
w=[]
str=raw_input().split()
for i in range(0,m):
v.append(int(str[i]))
v=sorted(v)
if(m>n):
a=m-n
else:
a=0
b=0
for i in range(a,m):
w.append((m-b)*v[i])
b+=1
print v[w.index(max(w))]

按层打印二叉树

题目描述

给定一棵二叉树的前序(根、左、右)和中序(左、根、右)的打印结果,输出此二叉树按层(从左往右)打印结果。
例如一棵二叉树前序:1 2 4 5 3;中序:4 2 5 1 3。可以构建出下图所示二叉树:

按层打印的结果则为:1 2 3 4 5。

输入

第一行只有一个数字,表示二叉树的节点数n(1<=n<=1000);
第二行由a1,a2,…,an(1<=ai<=1000)组成的整数序列(用空格分隔)—表示前序打印结果;
第三行由b1,b2,…,bn(1<=bi<=1000)组成的整数序列(用空格分隔)—表示中序打印结果。

输出

c1,c2,…,cn,用空格分隔—表示按层打印的结果。

样例输入

5
1 2 4 5 3
4 2 5 1 3

样例输出

1 2 3 4 5

分析与代码

之前遇到过树的题目都不太敢做,因为一想到数据结构的树类一大串代码就心累,今天拿着这大串代码开始删,发现其实可以不构建树类,只要构建结点类就好了。因为树说到底,就是结点连接了另外两个结点。这样下来,构建树的代码量就少了很多。然后,用前序遍历和中序遍历构建树,其实很简单,只要在中序遍历中递归寻找父结点,然后在前序遍历中递归插入。而层次遍历,只要每次从层数0到叶节点,判断层数,输出就好。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>

typedef struct node
{
int data;
struct node *lchild,*rchild;
}node;

node *creat(int *pre,int *in,int n)
{
int k;
int *p;
if(n<=0)
return NULL;
node *T=new node;
T->data=*pre;
for(p=in;p<in+n;p++)
{
if(*pre==*p)
break;
}
k=p-in;
T->lchild=creat(pre+1,in,k);
T->rchild=creat(pre+k+1,p+1,n-k-1);
return T;
}


int traversal(struct node *T,int level)
{
if(!T||level<0)
return 0;
if(level==0)
{
printf("%d ",T->data);
return 1;
}
return traversal(T->lchild,level-1)+traversal(T->rchild,level-1);
}

void level(struct node *T)
{
for(int i=0;;i++)
{
if(!traversal(T,i))
break;
}
}

int main()
{
int n;
scanf("%d",&n);
int *pre=new int(n);
int *in=new int(n);
node *T;
for(int i=0;i<n;i++)
{
scanf("%d",&pre[i]);
}
for(int i=0;i<n;i++)
{
scanf("%d",&in[i]);
}
T=creat(pre,in,n);
level(T);
printf("\n");
delete pre;
delete in;
return 0;
}

进制转换

题目描述

用英文字母a-z来分别表示数值0-25, 形成一个26进制的数值表示法。需要你写一个方法,将用a-z表示的26进制数值的字符串,转化为对应的10进制数值。

输入

输入数据有多组,每组占一行,包含多个a-z之间的字符。

输出

所对应表示的10进制数。

样例输入

ba
bcd
gibbon
goodboy

样例输出

26
731
74962693
2026285376

分析与代码

题目很简单,其实只要将其对应的ASCII值转化,然后乘上相应的位数次方就好了,代码:

1
2
3
4
5
6
7
8
str=raw_input()
while(str):
str=str[::-1]
sum=0
for i in range(0,len(str)):
sum+=(ord(str[i])-97)*(26**i)
print sum
str=raw_input()

简单弹球游戏

w和h为矩形的宽和高,x为起始的横坐标,n为反弹回来的次数,弹球每次发射时的角度为45度。
当时看到题目后,就开始想着分情况讨论了,结果越分越多,最后快没时间了,自己也快爆炸了……
今天,看到赛码网的讨论,很有帮助,原讨论在此,建立二位坐标系,模拟球的运动,因为每次反弹都是45度,所以一旦过界的话,只要将过界坐标取反就可以了,最后算出坐标:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>

void ball(int w, int h, int x, int n)
{
int y = 0;
int vx = 1, vy = 1;

while(n > 0) {

x += vx;
y += vy;

if (x >= w || x <= 0) {
vx = -vx;
}

if (y >= h || y <= 0) {
vy = -vy;
}

if (y <= 0) {
printf("%d ", x);
--n;
}
}

printf("\n");
}

int main()
{
int w, h, x, n;
while(scanf("%d%d%d%d", &w, &h, &x, &n) != EOF) {
ball(w, h, x, n);
}
}

时间转换

题目给的时分秒,24小时制,然后是一个分钟数,可正负,正数为往前推,负数为往后倒。

输入:
    23:55:00,600
输出:
    00 05 00

自己当时写的时候,也注意到了负数和过界的问题,可以最后的通过率好像是67%还是70%,很奇怪,要是发现问题,拜托跟我说下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//我自己的代码
#include <stdio.h>
#include <stdlib.h>

void get_time(int *hour, int *min, int *second, int const time_diff_second)
{
int diff_second=time_diff_second;
*hour+=diff_second/3600;
if(*hour<0)
{
while(*hour<0)
*hour+=24;
}
*hour%=24;
if(*hour>23)
*hour%=24;
diff_second%=3600;
*min+=diff_second/60;
if(*min<0)
{
*min=(*min+60)%60;
(*hour)--;
if(*hour<0)
*hour=(*hour+24)%24;
}
if(*min>59)
{
*min%=60;
(*hour)++;
if(*hour>23)
*hour%=24;
}
diff_second%=60;
*second+=diff_second;
if(*second<0)
{
*second%=60;
(*min)--;
if(*min<0)
{
*min=(*min+60)%60;
(*hour)--;
if(*hour<0)
*hour=(*hour+24)%24;
}
}
else if(*second>59)
{
*second%=60;
(*min)++;
if(*min>59)
{
*min%=60;
(*hour)++;
if(*hour>23)
*hour%=24;
}
}
}

int main()
{
int hour, min, second, time_diff_second;
while (scanf("%d:%d:%d,%d", &hour, &min, &second, &time_diff_second) != EOF)
{
get_time(&hour, &min, &second, time_diff_second);
printf("%02d %02d %02d\n", hour, min, second);
}
return 0;
}

然后是赛码网上讨论给出的一份代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>

int get_time(int *, int *, int *, int const);
int checkData(int, int, int);

int main(int argc, const char * argv[]) {

int hour, min, second, time_diff_second;

while (scanf("%d:%d:%d,%d", &hour, &min, &second, &time_diff_second) != EOF) {

get_time(&hour, &min, &second, time_diff_second);
printf("%02d %02d %02d\n", hour, min, second);
}
return 0;
}

int checkData(int h, int m, int s)
{
int ret = 0;

if (h < 0
|| h > 23)
{
ret = -1;
}
else if (m < 0
|| m > 59)
{
ret = -2;
}
else if (s < 0
|| s > 59)
{
ret = -3;
}

return ret;
}

int get_time(int *hour, int *min, int *second, int const time_diff_second)
{
int ret = 0;
int h = *hour, m = *min, s = *second;

ret = checkData(h, m, s);
if (ret != 0) {
return ret;
}

int a_min_second = 60;
int an_hour_second = 60 * a_min_second;
int a_day_second = 24 * an_hour_second;

int hour_second = h * an_hour_second;
int min_second = m * a_min_second;

int total_second = hour_second + min_second + s;
int trans_second = total_second + time_diff_second;

s = trans_second < 0 ? a_day_second - abs(trans_second % a_day_second) : trans_second;

h = (int)(s / an_hour_second);
s = s - (h * an_hour_second);

m = (int)(s / a_min_second);
s = s - (m * a_min_second);

*hour = h >= 24 ? h % 24 : h;
*min = m;
*second = s;

return ret;
}

自己再研究研究。

N皇后冲突个数

题目给出N个皇后的位置,计算出其中发生冲突的对数,不考虑中间隔挡,国际象棋中,皇后可以横竖斜,所以只要判断一下几种情况就好了:

输入
5
1 1
2 2
3 3
1 3
3 1
输出
10

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>

int judge(int x1,int y1,int x2,int y2)
{
if(((x2-x1)==(y2-y1))||((x2-x1)==(y1-y2))||(x1==x2)||(y1==y2))
return 1;
return 0;
}

int main()
{
int n,sum=0;
scanf("%d",&n);
int (*p)[2] = new int[n][2];
for(int i=0;i<n;i++)
scanf("%d %d",&p[i][0],&p[i][1]);
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
sum+=judge(p[i][0],p[i][1],p[j][0],p[j][1]);
}
}
printf("%d\n",sum);
delete p;
return 0;
}

数字翻转

两个数字翻转相加之后再翻转,如果有0的话,翻转之后应该是没有的。

样例输入:
123 450
样例输出:
573

人生苦短,我用python,直接用python的切片,强制转换,就好了,代码很简单:

1
2
3
4
5
a=raw_input().split()
b=a[1];
a=a[0];
c=str(int(a[::-1])+int(b[::-1]))
print int(c[::-1])

乘积最大

题目描述

有一个整数n,将n分解成若干个不同自然数之和,问如何分解能使这些数的乘积最大,输出这个乘积m

输入

一个整数

输出

一个整数

样例输入

15

样例输出

144

代码

题目要求是分解成不同的自然数,所以不是先尽量分解成3,再分解成2或4。由于原理跟相同的相似,即从2开始分解,每次递增1分解,因为分解数之间越接近乘积便越大,而当分解到最后剩余一个无法再往后分解的数时(假设为n),则将最后n个数都自加1,因为这样就能保证分解数之间的充分接近,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
int main()
{
int a[51];
int n;
scanf("%d",&n);
int sum=0,l=0,left,h=1;
for(int i=2;i<=n;i++)
{
a[l++]=i;
sum+=i;
if(sum>n)
{
sum-=i,l--,left=n-sum;
break;
}
}
for(int i=l-1;left;left--)
{
a[i]++;
i--;
if(i<0) i=l-1;
}
for(int i=0;i<=l-1;i++)
h*=a[i];
printf("%d\n",h);
return 0;
}

一分一毛,也是心意。