881. 救生艇-快速排序加贪心算法
2023-09-14 09:06:52 时间
881. 救生艇
给定数组 people 。people[i]表示第 i 个人的体重 ,船的数量不限,每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。
示例 1:
输入:people = [1,2], limit = 3
输出:1
解释:1 艘船载 (1, 2)
示例 2:
输入:people = [3,2,2,1], limit = 3
输出:3
解释:3 艘船分别载 (1, 2), (2) 和 (3)
示例 3:
输入:people = [3,5,3,4], limit = 5
输出:4
解释:4 艘船分别载 (3), (3), (4), (5)
解题代码如下:
void quick(int *a,int low,int high){
if(low<high){
int l=low,h=high,p=a[low];
while(low<high){
while(low<high&&a[high]>=p){
high--;
}
a[low]=a[high];
while(low<high&&a[low]<=p){
low++;
}
a[high]=a[low];
}
a[low]=p;
quick(a,l,low-1);
quick(a,low+1,h);
}
}
int numRescueBoats(int* people, int peopleSize, int limit){
quick(people,0,peopleSize-1);
int count=0;
int i;
int r[peopleSize];
for(i=peopleSize-1;i>=0;i--){
r[i]=1;
}
int l=0,h=peopleSize-1;
for(i=0;i<peopleSize;i++){
int val=people[i];
while(people[h]+val>limit){
h--;
if(h<=l){
break;
}
}
if(h<=l){
break;
}
r[h]=0;
r[l]=0;
count++;
l++;
h--;
}
for(i=0;i<peopleSize;i++){
// printf("%d ",r[i]);
if(r[i]==1){
count++;
}
}
return count;
}
相关文章
- Python 一网打尽<排序算法>之从玩转冒泡排序开始
- 详解快速排序算法
- 排序算法小结
- 八大排序算法(C语言实现)
- 用C语言实现快速排序算法「建议收藏」
- 快速排序(三种算法实现和非递归实现)
- 《算法竞赛进阶指南》0x27 A-star
- LM算法代码_快速排序算法代码
- 算法学习之路 | 快速排序[Php]
- 快速排序算法详解
- 必须知道的八大种排序算法【java实现】(一) 冒泡排序、快速排序详解编程语言
- javascript中两种基本常用排序算法分析详解编程语言
- MySQL排序算法:优化查询效率(mysqlin按顺序)
- MySQL的两种排序算法快速排序和归并排序(mysql两种排序算法)
- php数据结构算法(PHP描述)简单选择排序simpleselectionsort
- php数据结构与算法(PHP描述)快速排序quicksort
- php排序算法(冒泡排序,快速排序)
- 一个快速排序算法代码分享
- c语言快速排序算法示例代码分享
- c语言实现冒泡排序、希尔排序等多种算法示例
- PHP快速排序算法详解
- C语言实现排序算法之归并排序详解
- Java中常用的6种排序算法详细分解