网站建设犭金手指a排名15,天津网站排名方案,福州市建设工程工料机信息网站,wordpress与新浪博客租车骑绿岛
真题目录: 点击去查看 E 卷 100分题型 题目描述
部门组织绿岛骑行团建活动。租用公共双人自行车#xff0c;每辆自行车最多坐两人#xff0c;最大载重M。给出部门每个人的体重#xff0c;请问最多需要租用多少双人自行车。
输入描述
第一行两个数字m、n…租车骑绿岛
真题目录: 点击去查看 E 卷 100分题型 题目描述
部门组织绿岛骑行团建活动。租用公共双人自行车每辆自行车最多坐两人最大载重M。给出部门每个人的体重请问最多需要租用多少双人自行车。
输入描述
第一行两个数字m、n分别代表自行车限重部门总人数。
第二行n个数字代表每个人的体重体重都小于等于自行车限重m。
0m2000n1000000
输出描述
最小需要的双人自行车数量。
用例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
#includeiostream
#includevector
#includestring
#include utility
#include sstream
#includealgorithm
using namespace std;int main() {int m, n;cin m n;int res 0;vectorint 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 (bufiofmtossortstrconvstrings
)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--leftres}}fmt.Println(res)
}
