Question

有一道C语言的题目请教~~求高效算法~！！！

Input
第一行为T(T<20)，表示有T个公司。
接下来每个公司第一行为整数n(n<10^5)，表示该公司提供了n份金额不同的薪水。
第二行为n个整数，表示这n份不同的薪水。
第三行为整数m(m<10^5)，表示有m个人去面试。
第四行为m个整数，表示这m个人的期望薪水。

Output
对每个人输出一行，表示公司提供的最接近该面试者期望薪水的薪水。
每个公司之间用空行隔开。

Sample Input

1
5
1 2 3 4 5
3
2 4 6

Sample Output

2
4
5
面对同样接近的两份薪水，该公司会提供低薪水的职位给你，以节省经费。
公司提供的薪水和面试者的期望薪水都是无序的。
不好意思啊~~刚才忘了这个条件

Answer 1

不知这样可否：调用库函数中的quicksort（）分别对N和M这两组数据建行排序；
然后修改折半排序的 判读（具体怎么判定那就看你怎么设计了） 条件，进行选择，时间复杂度为（M*log2 (n))!（n为m 与N中的较大值）不过排序时也要时间哦！但是M和N都可能比较大，我觉得先排序在查找比较好，呵呵....

你应该也是搞ACM的吧？

当然，本人个人觉得本题在某种意义上说，要揣测出题的测试数据才能设计出最好的算法...~~

Answer 2

我是数痴啊，可别问我

Answer 3

慢慢写能写得出#35烦琐

Answer 4

下面，水品就这点，不是很精切。凑合。
#include<stdio.h>
void output(int t,int a[],int b[],int,int);
int main()
{
int T,i,j,n,a[80];
printf("请输入公司数目不超过20\n");
scanf("%d",&T);
if(T>20)
return 0;
for(i=1;i<=T;i++)
{
printf("输入该公司%d提供的薪水数目n",i);
scanf("%d",&n);
if(n>80)
return 0;////////////////////////////////////////薪水数不超过80，定义才最高80
for(j=0;j<n;j++)
{
printf("输入该公司提供的薪水%d:",j+1);
scanf("%d",&a[j]);
}
printf("\n\n");
}
int m,k,b[80];
printf("请输入来应聘的人数m");
scanf("%d",&m);
for(k=0;k<m;k++)
{
printf("输入%d 的应聘期望薪水",k+1);
scanf("%d",&b[k]);
}
output(T,a,b,80,m);
return 0;
}
void output(int t,int a[],int b[],int i,int m)
{
int k,j;
for(k=1;k<=m;k++)
for(j=1;j<=t;j++)
{
if(a[k]>a[j]-500)////////////////////////////////////////////////////////接近多少算期望自己调
printf("最接近该应聘者%d期望工资%d的是公司%d\n",k,a[j],j);
else
printf("无适合该应聘者%d的工资",k);
}
}

Answer 5

#include<iostream>
#include<vector>
using namespace std;
#include<stdio.h>
void* testp=freopen("test.txt","rt",stdin);

void main()
{
int N;
cin>>N;
for(int i=0;i<N;i++)
{
int n;
cin>>n;
vector<int>vn;
int x;
for(int j=0;j<n;j++)
{
cin>>x;
vn.push_back(x);
}
int m;
cin>>m;
vector<int>vm;
int y;
for(int k=0;k<m;k++)
{
cin>>y;
vm.push_back(y);
}

vector<int> money;
for(k=0;k<m;k++)
{
int cur=vn[0];
int num=abs(vm[k]-cur);
for( int p=1;p<n;p++)
if(num>abs(vm[k]-vn[p]))
{
cur=vn[p];
num=abs(vn[p]-vm[k]);
}
money.push_back(cur);
}

for(int e=0;e<m;e++)
{
cout<<money[e]<<endl;
}
}

}

注：另外创建一个文本文档"test.txt“，里面存下输入内容，把该文件和上面的CPP文件放在一起即可（文件流读入数据,方便输入改动数据）

Answer 6

是C语言学完的课程设计吧 我们当时学完也有
并不难啊 自己耐心做做肯定能做出来的

Answer 7

无能为力，不好意思。