租车骑绿岛【C语言】
/* 【租车骑绿岛】 部门组织绿岛骑行团建活动。租用公共双人自行车,每辆自行车最多坐两人,最大载重m。 给出部门每个人的体重,请问最多需要租用多少双人自行车。 输入描述: 第一行两个数字m、n,分别代表自行车限重,部门总人数。 第二行,n个数字,代表每个人的体重,体重都小于等于自行车限重m。 0<m<=200 0<n<=1000000 输出描述: 最小需要的双人自行车数量。 示例1 3 4 3 2 2 1 输出 3 */ #include <stdio.h> #include <stdlib.h> //比较函数 int compare(const void*a,const void* b){ return *(int*)a - *(int*)b; } int main(){ int weight[200]; int m,n; //初始值输入 scanf("%d %d",&m,&n); for(int i = 0; i < n; i++){ int a; scanf("%d",&a); weight[i] = a; } //快排 qsort(weight, n, sizeof(int), compare); //双指针设置 int left = 0; int right = n - 1; int nums = 0; int sum_weight = weight[left] + weight[right]; //最重的和最轻的加一起,如果比车载重大,表示最重的那个只能自己一个人单独骑一辆车,nums++,right-- //最重的和最轻的加一起,如果小于等于车载重,表示他们两个可以骑同一辆车, nums++,left++ ,right-- while(left < right){ if(sum_weight > m){ right--; nums++; sum_weight = weight[left] + weight[right]; } else{ right--; left++; nums++; sum_weight = weight[left] + weight[right]; } } //最后如果就剩一个人了还要加一辆车 if(left = right){ nums++; } printf("%d",nums); return 0; }
下一篇:
斐波那契-大数加法-数组解法