租车骑绿岛

租车骑绿岛

真题目录: 点击去查看

E 卷 100分题型

题目描述

部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，最大载重M。给出部门每个人的体重，请问最多需要租用多少双人自行车。

输入描述

第一行两个数字m、n，分别代表自行车限重，部门总人数。

第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。

• 0<m<=200
• 0<n<=1000000

输出描述

最小需要的双人自行车数量。

用例1

输入

3 4
3 2 2 1

输出

3

说明

无

题解

本题需要最少的车辆，即尽可能组合出重量小于等于m的两人组。贪心算法 + 双指针

• 按体重进行升序排序。left 只想最小体重， right指向最大体重。
  • arr[left] + arr[right] <= m left ++, right –
  • arr[left] + arr[right] > m right – , 优先减少体重大的

c++

#include <ios>
#include<iostream>
#include<vector>
#include<string>
#include <utility> 
#include <sstream>
#include<algorithm>
using namespace std;int main() {int m, n;cin >> m >> n;int res= 0;vector<int> ans(n);for (int i = 0; i < n; i++) {cin >> ans[i];}// 排序sort(ans.begin(), ans.end());int right = n - 1;int left = 0;while (left <= right) {int tmp = ans[left] + ans[right];// 说明不能同时两个人乘坐if (tmp > m) {right--;res++;// 能够同时乘坐} else {right--;left++;res++;}}cout << res;return 0;
}

JAVA

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}System.out.println(getResult(arr, m));}public static int getResult(int[] arr, int m) {Arrays.sort(arr);int count = 0;int i = 0;int j = arr.length - 1;while (i < j) {if (arr[i] + arr[j] <= m) i++;j--;count++;}if (i == j) count++;return count;}
}

Python

# 输入获取
m, n = map(int, input().split())
arr = list(map(int, input().split()))# 算法入口
def getResult(arr, m, n):arr.sort()count = 0i = 0j = n - 1while i < j:if arr[i] + arr[j] <= m:i += 1j -= 1count += 1if i == j:count += 1return count# 算法调用
print(getResult(arr, m, n))

JavaScript

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
rl.on("line", (line) => {lines.push(line);if (lines.length === 2) {const [m, n] = lines[0].split(" ").map(Number);const arr = lines[1].split(" ").map(Number);console.log(getResult(arr, m, n));lines.length = 0;}
});function getResult(arr, m, n) {arr.sort((a, b) => a - b);let count = 0;let i = 0;let j = arr.length - 1;while (i < j) {if (arr[i] + arr[j] <= m) i++;j--;count++;}if (i === j) count++;return count;
}

Go

package mainimport ("bufio""fmt""os""sort""strconv""strings"
)func main() {// 读取输入scanner := bufio.NewScanner(os.Stdin)scanner.Scan()firstLine := strings.Split(scanner.Text(), " ")m, _ := strconv.Atoi(firstLine[0])n, _ := strconv.Atoi(firstLine[1])scanner.Scan()inputNumbers := strings.Split(scanner.Text(), " ")ans := make([]int, n)for i := 0; i < n; i++ {ans[i], _ = strconv.Atoi(inputNumbers[i])}// 排序sort.Ints(ans)res := 0right := n - 1left := 0for left <= right {tmp := ans[left] + ans[right]// 说明不能同时两个人乘坐if tmp > m {right--res++// 能够同时乘坐} else {right--left++res++}}fmt.Println(res)
}