公司组织团建活动，到某漂流圣地漂流，现有如下情况：
员工各自体重不一，第 i 个人的体重为 people[i]，每艘漂流船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
为节省开支，麻烦帮忙计算出载到每一个人所需的最小船只数(保证每个人都能被船载)。
[编程题]漂流船问题
people = sorted(list(map(int, input().split()))) limit = int(input()) i, j, num = 0, len(people)-1, 0 while(i<j): if people[i]+people[j]<=limit: i+=1;j-=1;num+=1 else: j-=1;num+=1 print(num+1 if i==j else num)
编辑于 2019-07-09 11:20:53
回复(1)
#include<stdio.h>
#include<iostream>
#include<list>
#include<string>
#include<algorithm>
using namespace std;
int main(){
list<int> test;
int a[100]={0},i=0,temp=0;
int limit;
while(cin>>a[i++],cin.get()!='\n')
{temp++;}
temp=temp+1;
cin>>limit;
for(int i=1;i<temp;i++){
for(int j=i;j>0&&a[j]<a[j-1];j--){
swap(a[j],a[j-1]);
}
}
for(int i=0;i<temp;i++){
test.push_back(a[i]);
}
int c=0;
while(! test.empty())
{
if((test.front()+test.back())<=limit)
{
c++;
test.pop_front();
test.pop_back();
}
else{
c++;
test.pop_back();
}
if(test.size()==1){
c++;
break;
}
}
cout<<c;
return 0;
}
void swap(int a, int b)
{
int temp=a;
a=b;
b=temp;
}
#include<iostream>
#include<list>
#include<string>
#include<algorithm>
using namespace std;
int main(){
list<int> test;
int a[100]={0},i=0,temp=0;
int limit;
while(cin>>a[i++],cin.get()!='\n')
{temp++;}
temp=temp+1;
cin>>limit;
for(int i=1;i<temp;i++){
for(int j=i;j>0&&a[j]<a[j-1];j--){
swap(a[j],a[j-1]);
}
}
for(int i=0;i<temp;i++){
test.push_back(a[i]);
}
int c=0;
while(! test.empty())
{
if((test.front()+test.back())<=limit)
{
c++;
test.pop_front();
test.pop_back();
}
else{
c++;
test.pop_back();
}
if(test.size()==1){
c++;
break;
}
}
cout<<c;
return 0;
}
void swap(int a, int b)
{
int temp=a;
a=b;
b=temp;
}
发表于 2018-11-22 00:34:37
回复(0)
这个题目直接贪心就好了，只要把第一行的放进一个数组里面然后从小到大排序，然后存进一个栈里面去，循环直到栈为空，设置一个和sum，当sum大于或者等于船的最大承载量的时候计数加一，如果是大于就要把栈顶元素再放回去，有一个坑点就是最后要是sum不为0还需要加一。代码如下：
#include<bits/stdc++.h>usingnamespacestd;intgetN(string str){intsum=0;for(inti=0;i<str.length();i++){sum=sum*10+str[i]-'0';}returnsum;}intmain(){charstr[10005];intweith;/*getline(str,1005);cin>>weith;*/gets(str);//getchar();cin>>weith;vector<int> val;charch;string temp;for(inti=0;i<strlen(str);i++){if(str[i]!=' '){temp+=str[i];}else{intt=getN(temp);//cout<<t<<endl;val.push_back(t);temp="";}}val.push_back(getN(temp));sort(val.begin(),val.end());stack<int> st;for(inti=val.size()-1;i>=0;i--)st.push(val[i]);intcnt=0,sum=0;while(!st.empty()){intkk=st.top();//cout<<kk<<endl;sum+=st.top();st.pop();if(sum>=weith){cnt++;if(sum>weith)st.push(kk);sum=0;}}if(sum)cnt++;cout<<cnt<<endl;return0;}
发表于 2019-02-17 15:56:07
回复(0)
贪心
将人的体重升序排列，划分为“体重<=limit/2”的左半部分和“体重>limit/2”的右半部分。然后双指针求解，L指针指向左半部分最后一个人，R指针指向右半部分第一个人。
- 如果两人的体重<=limit就右移右指针，直到people
[L]无法再与右半部分的人配对，此时能够搞定右边rightSolved个人就表示左边也能搞定rightSolved个人，占用rightSolved条船。然后左指针向左移动rightSolved个位置。 - 如果一个右边的人都配对不了，就增加一个左半部分搞不定的人leftNoSolved，左移左指针，直到左指针越界。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String
[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String
[] strs = br.readLine().split(" ");
int n = strs.length;
int
[] people = new int
[n];
for(int i = 0; i < n; i++){
people
[i] = Integer.parseInt(strs
[i]);
}
Arrays.sort(people);
int limit = Integer.parseInt(br.readLine());
int lessR = lowerBound(people, limit >> 1); // 找到最后一个小于等于limit/2的位置
int L = lessR;
if(L == n){
// 全是小于limit/2的体重，直接两个人一艘船
System.out.println((n + 1) >> 1);
}else{
int R = L + 1;
int leftNoSolved = 0; // 左边没搞定的人
int rightSolved = 0; // 右边搞定的人
while(L >= 0){
while(R < n && people
[L] + people
[R] <= limit){
R++;
rightSolved++;
}
if(rightSolved == 0){
// L和右边的人配对一个都搞不定
leftNoSolved++; // 添加一个没搞定的人
L--; // 左移左指针
}else{
L = Math.max(-1, L - rightSolved);
}
}
int leftAll = lessR + 1;
int rightUnsolved = n - leftAll - rightSolved;
System.out.println(rightSolved + ((leftNoSolved + 1) >> 1) + rightUnsolved);
}
}
private static int lowerBound(int
[] nums, int target) {
int left = 0, right = nums.length, index = right;
while(left < right){
int mid = left + ((right - left) >> 1);
if(nums
[mid] > target){
right = mid - 1;
}else{
index = mid;
left = mid + 1;
}
}
return index;
}
}
编辑于 2022-01-16 15:48:01
回复(0)
参考了大家的思路，自己写了一篇C的，C真的还是要麻烦一些😂😂
#include<stdio.h>
#include<math.h>
#define MAXLENGTH 100000
int main()
{
int dataBuffer[MAXLENGTH];
int maxLoad;
int p = 0, count = 0;
while (scanf("%d", &dataBuffer[p++]))
{
if (getchar() == '\n')
break;
}
scanf("%d", &maxLoad);
count = p;
int i, j, temp;
//冒泡排序算法：进行 n-1 轮比较
for(i=0; i<count-1; i++)
{
for(j=0; j<count-1-i; j++)
{
if(dataBuffer[j] >dataBuffer[j+1])
{
temp = dataBuffer[j];
dataBuffer[j] = dataBuffer[j+1];
dataBuffer[j+1] = temp;
}
}
}
int a = 0;
int b = count-1;
int c = 0;
while(a<b)
{
if(dataBuffer[a]+dataBuffer[b] <= maxLoad)
{
a++;
b--;
} else
{
b--;
}
c++;
}
printf("%d",c + (a==b?1:0) );
}
发表于 2020-06-01 15:18:12
回复(0)
/*
我的想法，先排序，然后开始找同伴
*/
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
String str = input.nextLine();
String[] arr = str.split(" ");
int[] people = new int[arr.length];
for(int i = 0;i<arr.length;i++){
people[i] = Integer.parseInt(arr[i]);
}
int limit = input.nextInt();
//先排序
Arrays.sort(people);
int count = 0;//船的数量，上船的人这个会加一，他的体重也会被成-1
for(int i = 0;i<people.length;i++){
if(people[i]!=-1){//如果这个人没有上船
int right = people.length-1;
while(right>i){
if(people[right]!=-1){
if(people[i]+people[right]<=limit){
people[i]=-1;
people[right]=-1;
count++;
break;
}
}
right--;
}
if(people[i]!=-1)count++;
}else
continue;
}
System.out.println(count);
}
}
发表于 2020-04-20 16:04:35
回复(0)
参考其他人的代码，加了点自己的理解
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String[] people = input.nextLine().split(" ");
int limit = input.nextInt();
Arrays.sort(people);
int l = 0;
int r = people.length - 1;
int res = 0;
while (l < r) {
// 目前最大和最小能一起坐船
if (Integer.parseInt(people[l]) + Integer.parseInt(people[r]) <= limit) {
l++;
r--;
} else { // 最大和最小没法坐一条船，最大只能自己坐一条船
r--;
}
res++;
}
// 如果最后还剩一个人，再派一条船
if (l == r) {
res++;
}
System.out.println(res);
}
}
发表于 2020-02-22 11:00:49
回复(0)
//双端队列
#include <bits/stdc++.h>
using namespace std;
int main(){
int limit,sum=0;
deque<int> arr;
while(1){
int t;
cin>>t;
arr.push_back(t);
if(cin.get()=='\n')
break;
}
cin>>limit;
sort(arr.begin(),arr.end());
while(!arr.empty()){
if(arr.begin()==arr.end()-1)
arr.pop_back();
else if(arr.front()+arr.back()>limit)
arr.pop_back();
else{
arr.pop_front();
arr.pop_back();
}
sum++;
}
cout<<sum;
return 0;
}
发表于 2019-10-14 11:27:03
回复(0)
贪心 。先排序，然后尽可能让最胖的和最瘦的配对上船，否则胖的单独上船
#include<bits/stdc++.h>
using namespace std;
vector<int> a;
string line;
int w, tmp;
void read_data() {
getline(cin, line);
istringstream iss(line);
while(iss >> tmp)
a.push_back(tmp);
scanf("\n%d", &w);
}
int main() {
read_data();
sort(a.begin(), a.end());
int left = 0, right = a.size() - 1, res = 0;
while(left <= right) {
if(a[left] + a[right] <= w) {
left++; right--; res++;
} else {
right--; res++;
}
}
cout<<res<<endl;
}
/*
1 2 3
3
*/
发表于 2019-10-06 15:31:18
回复(0)
给一个很简单的思路吧：把体重先排序并默认一个人一条船；从最轻的人开始，找一个剩下最重的人拼船，找到了船就减一，没找到那后面更重的人也不可能找到了伙伴了直接break；
#include<iostream>
#include<vector>#include<algorithm>
using namespace std;
int main()
{
int x;
vector<int>a;
while(cin>>x)
{
a.push_back(x);
if(cin.get()=='\n')break;
}
int n;
cin>>n;
int len=a.size();
sort(a.begin(),a.end());
int sum=len;
int y=len-1;
for(int i=0;i<y;i++)
{
int t=n-a[i];
while(a[y]>t)y--;
if(y>i){sum--;y--;}
else break;
}
cout<<sum<<endl;
return 0;
}
发表于 2019-08-23 10:55:11
回复(0)
为什么最大体重加最小体重能保证船数最小，有没有大佬能解惑一下？☹
我的思路是尽量把每艘船承载的体重都接近limit值，哈希表实现
import java.io.*;
import java.util.Map;
import java.util.HashMap;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
String[] weight=in.readLine().split(" ");
String limits=in.readLine();
int n=weight.length;
if(n==0){
System.out.println("输入错误");
return;
}
int[] people=new int[n];
for(int i=0;i<n;++i){
people[i]=Integer.parseInt(weight[i]);
}
int limit=Integer.parseInt(limits);
//哈希表
Map<Integer,Integer> map=new HashMap<>();
int count=0;
for(int i=0;i<n;++i){
map.put(people[i],map.getOrDefault(people[i],0)+1);
}
for(int i=0;i<n;++i){
if(map.get(people[i])==0)
continue;
if(limit>=people[i]){
map.put(people[i],map.get(people[i])-1);
int temp=limit-people[i];
while(temp>0&&(map.get(temp)==null||map.get(temp)==0)){
temp--;
}
count++;
if(temp>0){
map.put(temp,map.get(temp)-1);
}
}
}
System.out.println(count);
}
}
发表于 2019-08-07 17:37:50
回复(0)
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] peoples = in.nextLine().split(" ");
int limit = in.nextInt();
int n = peoples.length;
int[] p = new int[n];
for (int i=0;i<n;i++){
p[i] = Integer.parseInt(peoples[i]);
}
Arrays.sort(p);
int i = 0, j = n-1;
int count = n;
while (i < j){
if (p[i] + p[j] <= limit){
count--;
i++;j--;
}
else
j--;
}
System.out.println(count);
}
}
发表于 2019-08-06 15:33:29
回复(0)
注意利用每艘船只能载两人，以及保证每个人都能被船载两个条件。
class Solution {
public int countLeastBoat(Integer []nums,int maxLoad){
Arrays.sort(nums);
int count = 0;
int i = 0;
int j = nums.length-1;;
while(i<j) {
if(nums[i]+nums[j] <= maxLoad) {
i++;
j--;
} else {
j--;
}
count++;
}
return count + (j==i?1:0);
}
}参考解答来源：
作者：qq_27181495
来源：CSDN
原文：https://blog.csdn.net/qq_27181495/article/details/84633499
版权声明：本文为博主原创文章，转载请附上博文链接！
编辑于 2019-03-19 13:22:03
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Solution9_漂流船问题 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] line1 = bf.readLine().split(" ");
int n = line1.length;
int limit = Integer.parseInt(bf.readLine());
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(line1[i]);
}
Arrays.sort(nums);
int count = 0;
int left = 0, right = n - 1;
while (left <= right) {
if (nums[left] + nums[right] > limit) { //两个人装不下，只能装后面那个胖子，右边指针左移
count++;
right--;
} else {//能装下，左右指针都移动
count++;
left++;
right--;
}
}
System.out.println(count);
}
}
发表于 2019-08-10 09:53:34
回复(1)
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> v;
int x, K;
char c;
while(1){
cin>>x;
v.push_back(x);
c = cin.get();
if(c=='\n')
break;
}
cin>>K;
sort(v.begin(), v.end());
int n = v.size(), cnt=0, i=0, j=n-1;
while(i<j){
if(v[i]+v[j]<=K)
i++;
cnt++;
j--;
}
if(i==j)
cnt++;
cout<<cnt<<endl;
return 0;
}
编辑于 2019-07-30 11:41:03
回复(0)
双指针做法
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> wei;
int n;
while (cin >> n) {
wei.push_back(n);
}
int boat = wei[wei.size() - 1];
sort(wei.begin(), wei.end() - 1);
int i = 0, j = wei.size() - 2;
int ans = 0;
while (i <= j) {
if (wei[i] + wei[j] <= boat)
i++;
j--;
ans++;
}
cout << ans;
}
// 64 位输出请用 printf("%lld")
发表于 2025-03-25 21:57:30
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] people = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int limit = in.nextInt();
Arrays.sort(people); // 升序
int cnt = 0;
for (int i = 0, j = people.length - 1; i <= j;) {
if (people[j] + people[i] <= limit) i++; // 最大 + 最小, 超重则大的单飞
cnt++;
j--;
}
System.out.print(cnt);
}
}
发表于 2025-02-04 18:41:50
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-01-08 17:12:41
-
2022-11-02 21:50:17
-
2022-10-30 17:09:00 -
2022-10-28 16:34:34 -
2022-10-28 14:25:33
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
