公司组织团建活动,到某漂流圣地漂流,现有如下情况:
员工各自体重不一,第 i 个人的体重为 people[i],每艘漂流船可以承载的最大重量为 limit。
每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。
为节省开支,麻烦帮忙计算出载到每一个人所需的最小船只数(保证每个人都能被船载)。
第一行输入参与漂流的人员对应的体重数组,
第二行输入漂流船承载的最大重量
所需最小船只数
1 2 3
1
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); } }
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)
#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;}
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; } }
#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) ); }
/* 我的想法,先排序,然后开始找同伴 */ 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); } }
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); } }
//双端队列 #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; }
#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 */
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); } }
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); } }
注意利用每艘船只能载两人,以及保证每个人都能被船载两个条件。
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
版权声明:本文为博主原创文章,转载请附上博文链接!
#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; }
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)
#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; }排序,选满足船载量的最小值和最大值
left
和right
指针向中间搜索left==right
,只剩下一个人,count+1
limit
,两个指针向中间移动,count+1
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)