首页 > ACM题库 > 九度OJ > 九度-1097-取中值[解题代码]
2013
12-12

九度-1097-取中值[解题代码]

题目来源:2009年上海交通大学计算机研究生机试真题

题目描述:

     存在两组数组,和4个数字a,b,c,d,要求做如下操作,将第一个数组第a个数到第b个数,第二个数组的第c个数到第d个数放到一个数组中,求出合并后数组的中间值,如果有两个中间值,取下标较小的那个。

输入:

    第一行一个整数t表示有t个测试数据
    第二行两个整数,表示两个数组的长度,
    接下来两行表示两个数字的值,

    最后一行有四个整数a,b,c,d。

    数组长度不会超过1000000。

输出:

    每行一个整数,对应合并数组的下标在中间的那个值。

样例输入:
1
5 4
1 2 3 4 5
6 7 8 9
1 2
1 3
样例输出:
6

cpp 代码如下:
#include <stdio.h>
#include <string.h>
int arr1[50001];
int arr2[50001];
int main() {
	int n,a,b,s1,e1,s2,e2,i;
	scanf("%d",&n);
	while(n--){
		scanf("%d %d",&a,&b);
		for( i=0; i<a; i++)
			scanf("%d",&arr1[i]);
		for( i=0; i<b; i++)
			scanf("%d",&arr2[i]);
		scanf("%d %d %d %d",&s1,&e1, &s2, &e2);
		int len=(e1-s1) + (e2-s2) + 2;
		memcpy(arr1,arr1+s1-1,(e1-s1+1)*sizeof(int));
		memcpy(arr1+(e1-s1+1),arr2+s2-1,(e2-s2+1)*sizeof(int));
		printf("%d\n",arr1[ (len-1) / 2]);
	}
	return 0;
}
/**************************************************************
	Problem: 1097
	User: coder
	Language: C
	Result: Accepted
	Time:40 ms
	Memory:1304 kb
****************************************************************/


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }