UC知道C语言问题 20分
来源：百度知道 编辑：UC知道 时间：2024/05/20 06:19:05
Lijiganjun和他的朋友去公园玩。他们到了“双人船码头”，准备去划船。顾名思义,双人船就是最多有两个人乘坐的船J为了安全起见，码头规定一艘船乘客的重量不能超过一个定值。由于Lijiganjun没有带太多的钱，他希望可以花最少的钱让大家都划上船，即租最少的船使大家都有船坐:P他希望你可以帮助他。
输入
文件”kaj.in”的第一行有一个整数w,80<=w<=200,是双人船的最大载重量.第二行有一个整数n,1<=n<=30000,是划船的总人数.以下的n行每行有一个整数p,5<=p<=w,是每一个人的重量.
输出
文件”kaj.out”只有一个数,最少需要租的船数.
样例
kaj.in kaj.out
100 6
9
90
20
20
30
50
60
70
80
90
最后 有详细说明+分
输入
文件”kaj.in”的第一行有一个整数w,80<=w<=200,是双人船的最大载重量.第二行有一个整数n,1<=n<=30000,是划船的总人数.以下的n行每行有一个整数p,5<=p<=w,是每一个人的重量.
输出
文件”kaj.out”只有一个数,最少需要租的船数.
样例
kaj.in kaj.out
100 6
9
90
20
20
30
50
60
70
80
90
最后 有详细说明+分
#include <stdio.h>
#include <stdlib.h>
int n,w;
int person[30000];
int cmp_int(const void* in1,const void *in2){
return *(int*)in1 - *(int*)in2;
}
int main(){
FILE *fi=fopen("kaj.in","r");
int i,j,w2,r;//r是计算结果
fscanf(fi,"%d%d",&w,&n);
for(i=0;i<n;i++){
fscanf(fi,"%d",&person[i]);
}
fclose(fi);
//从小到大排序
qsort(person,n,sizeof(int),cmp_int);
w2=w/2;
//考虑那些超过w/2重的人
for(i=0,j=n-1,r=0; i<j && person[j]>=w2; j--,r++){
if(person[i]+person[j]<=w)//重的可以和轻的搭一条船
i++;
//else{}重的单独一条船
}
//其余都是小于w/2的人，一定能2人一船
if(i<=j){
r+=(j-i)/2+1;//此时剩余人数(j-i+1),需要船((j-i+1)+1)/2
}
fi=fopen("kaj.out","w");
fprintf(fi,"%d\n",r);
fclose(fi);
return 0;
}
我提一下我个人思路:
1.将所有p降序排序