多易网络2017 春招编程题.pdf

1、多益网络多益网络 20172017 春招春招两个编程题两个编程题原文地址:http:/ 1 1 舍友做的，做完后我听了他的描述，自己写了一个解题程序也不知道对不对，毕竟不是在线 oj 不能查结果。题目描述，给题目描述，给 n,mn,m 两个数，两个数，n n 表示球队的个数（从表示球队的个数（从 1 1 到到 n n），mm 表示比赛表示比赛场数，然后给场数，然后给 mm 组数据，每组数据有两个数组数据，每组数据有两个数，（a,ba,b）即表示）即表示 a a 赢了赢了 b b，要求是输出一种排列方式，使得不存在排在前面的队输过排在后面的队要求是输出一种排列方式，使得不存在排在前面的队输过排在

2、后面的队。如果有（如果有（a,ba,b）即）即 a a 一定在一定在 b b 前面。前面。我的想法是将这 m 场比赛视为 m 个不同的规则，初始化一个 count 数组，长度为 n，默认排列顺序为（1n）然后进行 m 次检验，如果（a,b）在现有的排列中不满足 a 在 b 的前面，则调换 a,b 的位置，否则不做处理。我试了下这个方法，发现有的数据不好使。取 n=5，m=5 五场比赛（2，3）（2，4）（1，2）（1，5）（5，2）排列的结果：1 2 3 4 5 比赛（2，3）满足顺序1 2 3 4 5 比赛（2，4）满足顺序1 2 3 4 5 比赛（1，2）满足顺序1 2 3 4 5 比赛（

3、1，5）满足顺序1 5 3 4 2 比赛（5，2）调整 2，5 位置 但是在这个地方会使 2 排在 3 4后面，以至于不满足前面的规则。随后进行了改进，把这个循环写成一个函数，sort 进行排序，排序完后进行 test，检查现在的结果是否满足要求，如果不满足，再进行一次 sort，若干次排序后一定会得到一个结果满足条件。代码如下：#include using namespace std;void soft(int count,int a2,int m,int n)for(int i=0;i m;i+)int j,k,temp;for(j=0;j n;j+)if(countj=ai0)break

4、;for(k=0;k k)temp=countj;countj=countk;countk=temp;bool test(int count,int a2,int m,int n)for(int i=0;i m;i+)int j,k;for(j=0;j n;j+)if(countj=ai0)break;for(k=0;k k)return false;return true;int main()int n,m;cinnm;int am2;for(int i=0;i ai0ai1;int countn;for(int i=0;i n;i+)counti=i+1;while(!test(count

5、,a,m,n)soft(count,a,m,n);for(int i=0;i n;i+)coutcounti;return 0;可能还是会有些情况没有考虑到，但是因为这个不是提交就能看结果的测评，所以没办法去验证。题目题目 2 2 给一个数组给一个数组 a=8a=8，3 3，5 5，2 2，7 7，4 4，6 6，11，要求用要求用 O(n)O(n)的时间的时间复杂度，复杂度，O(1)O(1)的空间复杂度做。的空间复杂度做。做法：申请一个 count 数组（所有元素为 0），保证数组的长度大于要排序的数组的最大元素，然后遍历数组 a，把 a 中每一个元素的值做为 count数组的下标，并使该下

6、标对应的数组元素的值自增。用空间换取时间的非典型排序方法。代码如下：#include using namespace std;void sort(int count,int a,int len)for(int i=0;i len;i+)countai+;for(int i=0,j=0;i 65536;i+)if(counti!=0)aj+=i;counti-;i-;void show(int a,int len)for(int i=0;i len;i+)coutai;using namespace std;int main()int count65536=0;int a=8,3,5,2,7,4,6,1;int len=sizeof(a)/sizeof(int);sort(count,a,len);show(a,len);return 0;