9504 面试
时间限制:2000MS 内存限制:65535K提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
近来acm各大神牛教主均已经拿到超级offer（腾讯、网易、迅雷、阿里巴巴，百度……），无限膜拜。 小菜Arokenda因平时不学无术，已经成为华农新一届面霸，记录正在不断刷新。经过2^n次面试，哥总结出，有80%的公司都会问你期望薪水为多少。 当然，他们公司原定计划都有N多不同金额的薪水，会根据你期望的薪水找到一份与你最匹配的薪水（即最接近你期望的薪水）， 当然，能否拿到必需至少具备有此二条件其中之一： 1、你是华农acmer且成为教主级人物。 2、你的忽悠能力灰常强。#^_^#
输入格式
第一行为T(T<20)，表示有T个公司。
接下来每个公司第一行为整数n(n<
5000)，表示该公司提供了n份金额不同的薪水。
第二行为n个整数，表示这n份不同的薪水。
第三行为整数m(m<
5000)，表示有m个人去面试。
第四行为m个整数，表示这m个人的期望薪水。
输出格式
对每个人输出一行，表示公司提供的最接近该面试者期望薪水的薪水。
每个公司之间用空行隔开。
输入样例
2
5
1 2 3 4 5
3
2 4 6
5
1 2 3 4 5
3
2 4 6
输出样例
2
4
5
2
4
5
提示
面对同样接近的两份薪水，该公司会提供低薪水的职位给你，以节省经费。
公司提供的薪水和面试者的期望薪水都是无序的。 大水题，简单二分，无需做任何优化，在处理左右边界情况时注意分类别出错就行 了。
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <algorithm>
4
5 using namespace std;
6
7 void bin_search(
int a[],
int n,
int left,
int right)
8 {
9 int mid=(left+right)/
2;
10 if(a[mid]==
n)
11 printf(
"%d\n",a[mid]);
12 else if(mid==
left)
13 {
14 if(a[right]==
n)
15 printf(
"%d\n",a[right]);
16 else if(a[left]==
n)
17 printf(
"%d\n",a[left]);
18 else if(a[right]>
n)
19 {
20 int tl=n-a[mid],tr=a[right]-
n;
21 if(tl==
tr)
22 printf(
"%d\n",a[mid]);
23 else if(tl>
tr)
24 printf(
"%d\n",a[right]);
25 else printf(
"%d\n",a[mid]);
26 }
27 else if(a[right]<
n)
28 printf(
"%d\n",a[right]);
29 else if(a[left]>
n)
30 printf(
"%d\n",a[left]);
31 }
32
33 else if(a[mid]<
n)
34 bin_search(a,n,mid,right);
35 else if(a[mid]>
n)
36 bin_search(a,n,left,mid);
37 }
38
39 int main()
40 {
41 int T,n,m,i;
42 scanf(
"%d",&
T);
43 while(T--
)
44 {
45 int pay[
5000]={
0},want[
5000]={
0};
46 scanf(
"%d",&
n);
47 for(i=
0;i<n;i++
)
48 scanf(
"%d",&
pay[i]);
49 scanf(
"%d",&
m);
50 for(i=
0;i<m;i++
)
51 scanf(
"%d",&
want[i]);
52 sort(pay,pay+
n);
53 //
54 for(i=
0;i<m;i++
)
55 bin_search(pay,want[i],
0,n-
1);
56 putchar(
'\n');
57 }
58 return 0;
59 }
转载于:https://www.cnblogs.com/geek1116/p/5240304.html
相关资源：数据结构—成绩单生成器
