Question

C语言编程有关数组的

比基堡海滩有一个有n个触手的恐怖水母，蟹老板希望雇佣一些海绵宝宝把它杀死（即
砍掉所有触手）。现在有m个海绵宝宝可以雇佣，一个能力值为x的海绵宝宝可以砍掉恐怖水母一只直径不超过x的触手，且需要支付x个金币。如何雇佣海绵宝宝
才能杀死水母，并且支付的金币最少？需要注意一个海绵宝宝只能砍掉一只触手，并且不能被雇佣两次。

Input

第1行为正整数n和m，第2行为水母n只触手的直径，第3行为m个海绵宝宝的能力值，所有数据用空格间隔。

Output

输出最少金币数。如果无解，输出NULL

Answer 1

#include <stdio.h>
#include <stdlib.h>
int Partition(int *s, int left, int right)
{
int tmp = s[left];
while(left < right) {
while(left < right && s[right] >= tmp) right--;
s[left] = s[right];
while(left < right && s[left] <= tmp) left++;
s[right] = s[left];
}
s[left] = tmp;
return left;
}

void QSort(int *s, int left, int right) {
if(left < right) {
int q = Partition(s, left, right);
QSort(s, left, q - 1);
QSort(s, q + 1, right);
}
}

int main( ) {
int i, j, m, n, *Hand, *Sponge, Money = 0;

scanf("%d%d", &n, &m);
if(m < n) {
printf("NULL\n");
return 0;
}
Hand = (int *) malloc (n * sizeof(int));
Sponge = (int *) malloc (m * sizeof(int));
for(i = 0; i < n; i++)
scanf("%d", &Hand[i]);
for(i = 0; i < m; i++)
scanf("%d", &Sponge[i]);

QSort(Hand, 0, n - 1);
QSort(Sponge, 0, m - 1);
for(i = 0, j = 0; i < n && j < m; ) {
if(Sponge[j] >= Hand[i]) {
Money += Sponge[j];
i++, j++;
}
else j++;
}

if(i == n)
printf("%d\n", Money);
else
printf("NULL\n");

free(Hand);
free(Sponge);
return 0;
}

Answer 2

#include <stdio.h>

void sort(int a[], int n)
{
int i, j;

for(i = 0; i < n; i ++) {
for(j = i+1; j < n; j ++) {
if(a[i] > a[j])
{
a[i] += a[j];
a[j] = a[i] - a[j];
a[i] -= a[j];
}
}
}
}

main()
{
int m, n, *a, *b, i, j, money=0, bOK = 0;

printf("请输入水母的触手数量n和海绵宝宝的数量m:");
scanf("%d %d", &n, &m);

if(m < n) {
printf("NULL");
return;
}
a = (int *)malloc(n*sizeof(int));
b = (int *)malloc(m*sizeof(int));

if(a == 0 || b == 0) {
printf("内存错误\n");
return;
}

printf("请依次输入水母的%d个触手的直径值：", n);
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("请依次输入%d个海绵宝宝的的能力值：", m);
for(i = 0; i < m; i++)
scanf("%d", &b[i]);

sort(a, n);
sort(b, m);

for(i = 0, j = 0; i < n; i++) {
while(j < m) {
if(a[i] <= b[j]) {
money += b[j++];
if(i == n-1)
bOK = 1;
break;
}
j++;
}
if(j == m)
break;
}
free(a);
free(b);
if(bOK == 0)
printf("NULL");
else
printf("最少需要花费%d个金币\n", money);
}

Answer 3

听着挺复杂的，没搞定，等着看看其他人怎么解决，学习下。。。