漂流船问题_招商银行信用卡中心笔试题

十年单身换一个字节SP

这个题目直接贪心就好了，只要把第一行的放进一个数组里面然后从小到大排序，然后存进一个栈里面去，循环直到栈为空，设置一个和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)

lentolove

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)

Polestar_a

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)

xxshaonian

#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;
}

发表于 2018-11-22 00:34:37 回复(0)

Java

pein531

贪心

将人的体重升序排列，划分为“体重<=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++

树丫是个小软妹

参考了大家的思路，自己写了一篇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)

Java

lmz9509

/*
我的想法，先排序，然后开始找同伴
*/
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)

acqierement...

参考其他人的代码，加了点自己的理解

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)

C/C++

昔遥暮云

//双端队列
#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)

C/C++

卷积神经网络哦

贪心。先排序，然后尽可能让最胖的和最瘦的配对上船，否则胖的单独上船

#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)

C/C++

摆码王子星

给一个很简单的思路吧：把体重先排序并默认一个人一条船；从最轻的人开始，找一个剩下最重的人拼船，找到了船就减一，没找到那后面更重的人也不可能找到了伙伴了直接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)

Java

小能猫Tom

为什么最大体重加最小体重能保证船数最小，有没有大佬能解惑一下？☹

我的思路是尽量把每艘船承载的体重都接近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)

Java

呃。。。

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)

Python

ElonB

"""
贪心法，重配轻，直到都有船
"""

if __name__ == "__main__":
    people = list(map(int, input().strip().split()))
    limit = int(input().strip())
    people.sort()
    ans = 0
    while people:
        ans += 1
        t = limit - people.pop()
        if not people: break
        if t >= people[0]:
            people.pop(0)
    print(ans)

发表于 2019-07-11 10:01:21 回复(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)

初心者托奇

a = sorted(map(int,input().split()))
b,m,n,p = int(input()),0,len(a) - 1,0
while m <= n:
    if a[m] + a[n] <= b:
        m += 1
    n,p = n - 1,p + 1
print(p)

编辑于 2020-03-15 18:21:11 回复(0)

C/C++

nbgao

#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)

蓉蓉兔1996

笨办法。。。

people = list(map(int,input().split()));
limit = int(input());
num = 0;
max_weight = 0;

while len(people)!=0:
    flag = 0;
    max_weight = people[0];
    for i in range(1,len(people)):
        if ((people[0] + people[i]) > max_weight)&((people[0] + people[i] )<= limit):
            max_weight = people[0] + people[i];
            flag = 1;
            del_people = i
    num = num + 1;
    if flag==1:
        del people[0];
        del people[del_people-1];
    else:
        del people[0];
        
print(num)

编辑于 2021-03-25 20:18:00 回复(0)

牛客657960111号

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> weight;
    int n, limit;
    int ans = 0;
    while(cin>>n){
        weight.push_back(n);
        if(cin.get() == '\n'){
            break;
        }
    }
    cin>>limit;
    int len = weight.size();
    sort(weight.begin(),weight.end());
    int i = 0, j = len - 1;
    if(weight[j] > limit) 
        return 0;
    while(i < j){
        if(weight[i] + weight[j] <= limit){
            ans ++;
            len = len - 2;
            j --;
            i ++;
        }
        else{
            j --;
        }
    }
    ans += len;
    cout<<ans<<endl;
    return 0;
}

排序，选满足船载量的最小值和最大值

发表于 2020-09-18 22:00:32 回复(0)

Python

我不想当大白菜

，贪心：先排序然后使用left和right指针向中间搜索
- 如果left==right,只剩下一个人，count+1
- 如果和小于等于limit，两个指针向中间移动，count+1
- 否则，right位置的人超重了，单人一个船，count+1

nums = list(map(int,input().split()))
limit = int(input())

count = 0
nums = sorted(nums)
left,right = 0,len(nums)-1
while left <= right:
    if left == right :
        count += 1
        break
    elif nums[left]+nums[right]<=limit:
        left += 1
        right -= 1
    else:
        right -= 1
    count += 1
print(count)

发表于 2020-07-23 19:53:51 回复(0)

漂流船问题

输入描述:

输出描述:

输入

输出

贪心

问题信息

热门推荐

通过挑战的用户

相关试题