赞
踩
给定两个整数数组
array1 array2 数组元素按升序排列
假设从arr1 arr2中分别取出一个元素,可构成一对元素
现在需要取出k对元素,并对取出的所有元素求和
计算和的最小值
注意:两对元素对应arr1 arr2的下标是相同的
视为同一对元素
输入描述
输入两行数组arr1 arr2
每行首个数字为数组大小size 0<size<=100
arr1,2中的每个元素 0< <1000
接下来一行 正整数k 0<k<=arr1.size * arr2.size
输出描述
满足要求的最小值
例子
输入
3 1 1 2
3 1 2 3
2
输出
4
说明:用例中需要取两个元素,
取第一个数组第0个元素与第二个数组第0个元素组成一个元素
[1,1]
取第一个数组第1个元素与第二个数组第0个元素组成一个元素
[1,1]
求和为1+1+1+1=4 ,满足要求最小
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<math.h>
- int cmp(const void* a, const void* b)
- {
- return *(int*)a - *(int*)b;
- }
- void StrToList(char* s, int* list, int* n)
- {
- int idx = 0;
- char* p = strtok(s, " ");
- while (p != NULL)
- {
- p = strtok(NULL, " ");
- list[idx] = atoi(p);
- idx++;
- }
- *n = idx - 1;
- }
- int GetSum(int* arr1, int len1, int* arr2, int len2, int k)
- {
- int i, j, idx = 0;
- int* list = NULL;
- int len = sizeof(int) * len1 * len2;
- int result = 0;
- list = malloc(len);
- if (list == NULL)
- return -1;
- memset(list, 0, len);
- for (i = 0; i < len1; i++)
- {
- for (j = 0; j < len2; j++)
- {
- list[idx] = arr1[i] + arr2[j];
- idx++;
- }
- }
- qsort(list, len1*len2, sizeof(list[0]), cmp);
- for (i = 0; i < k; i++)
- {
- result += list[i];
- }
- printf("%d", result);
- free(list);
- }
- int main()
- {
- int k, len1 = 0, len2 = 0;
- char s1[100] = { 0 };
- char s2[100] = { 0 };
- int list1[100] = { 0 };
- int list2[100] = { 0 };
- gets(s1);
- gets(s2);
- scanf("%d", &k);
- StrToList(s1, list1, &len1);
- StrToList(s2, list2, &len2);
- GetSum(list1, len1, list2, len2, k);
- return 0;
- }
附录1:qsort用法
void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
base待排序数组首地址
nelem数组中待排序元素数量
width各元素的占用空间大小
fcmp指向函数的指针
功能:使用快速排序例程进行排序
时间复杂度:n*log(n)
自定义比较函数int cmp(const void* a, const void *b)
如果a > b比较函数返回大于0;如果a = b,返回0;如果 a < b,返回小于0;
对于整数
- int cmp(const void *a, const void *b)
- {
- return *(int*)a - *(int*)b;
- }
对于其他简单类型也可以用相似的方法
举例
- #include <stdio.h>
- #include <stdlib.h>
-
- int cmp(const void *a, const void *b)
- {
- return *(int *)a - *(int *)b;
- }
-
- int main()
- {
- const int len = 7;
- int index;
- int arr[len] = { 2, 3, 1, 7, 5, 4, 6 };
- printf("Before sort:\n");
- for (index = 0; index < len; ++index)
- {
- printf("%d ", arr[index]);
- }
- printf("\n");
-
- qsort(arr, len, sizeof(arr[0]), cmp);
-
- printf("After sort:\n");
- for (index = 0; index < len; ++index)
- {
- printf("%d ", arr[index]);
- }
- printf("\n");
-
- return 0;
- }
- /*
- 输出:
- Before sort:
- 2 3 1 7 5 4 6
- After sort:
- 1 2 3 4 5 6 7
- */
附录2:strtok(), strtok_s() 字符串分割函数
当strtok()在参数_Str的字符串中发现参数_Delim中包涵的分割字符时,则会将该字符改为\0 字符。
在第一次调用时,strtok()必需给予参数_Str字符串,往后的调用则将参数_Str设置成NULL。每次调用成功则返回指向被分割出片段的指针。
需要注意的是,使用该函数进行字符串分割时,会破坏被分解字符串的完整,调用前和调用后的s已经不一样了。
第一次分割之后,原字符串str是分割完成之后的第一个字符串,剩余的字符串存储在一个静态变量中。
- //将字符串"ab,cde,fghi"按照","分割。char str[] = "ab,cde,fghi";
- char *p[4];
- p[0]= strtok(str, ",");
- int i = 0;
- while (p[i] != NULL)
- {
- i++;
- p[i]= strtok(NULL, ",");
- }
- p[i] = "\0";
- for (int i = 0; i < 4; i++)
- {
- cout << p[i] << endl;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。