局域网建立网站教程,网站嵌入播放器,南京网站seo,做社区网站用什么程序好独木舟上的旅行Description进行一次独木舟的旅行活动#xff0c;独木舟可以在港口租到#xff0c;并且之间没有区别。一条独木舟最多只能乘坐两个人#xff0c;且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销#xff0c;所以要找出可以安置所有…独木舟上的旅行Description进行一次独木舟的旅行活动独木舟可以在港口租到并且之间没有区别。一条独木舟最多只能乘坐两个人且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则计算要安置所有旅客必须的最少的独木舟条数并输出结果。Input第一行包括两个整数wn80w200,1n300w为一条独木舟的最大承载量,n为人数接下来的一组数据为每个人的重量(不能大于船的承载量)Output输出所需要的最少独木舟的条数。Sample Input85 65 84 85 80 84 83Sample Output5好来一起思考一下这个问题有两个点必须记住一条船只能做两个人且两个人重量相加不能超过最大负载量。因此第一步我们先对n个人的体重进行从小到大排序然后从第一个开始如果第一个可以装的下且小于最大负载量则向后搜寻小于等于剩下重量空余承重的最大值作为与第一个坐同一艘船的人。设置一个bool类型数组把n个未上船的人的值置为true(初始化为true)然后已经上船的就置为false。然后向后进行循环结束所有人都上了船用count记录船数。#include#includeusing namespace std;int Greedy(int a[],bool b[],int n,int w){sort(a,an);//排序 (内置排序)int count 0;//记录元素从零开始for(int i 0;iif(a[i]wb[i]true){//如果此人重量不超标且未上船则进入在此数后面搜寻小于剩余量的最大值找到置为false表示此人与别人共上船。int m w-a[i];//剩余空余量for(int ji1;jif(jn-1a[j]m) {//解决最大值产生在最大一个的情况。b[j]false;//置为falsebreak;}if(a[j]ma[j1]m) {//找到最大值b[j]false;break;}}count;//记录元素为用船数}}return count;}int main(){int w;cinw;int n;cinn;int *anew int[n];bool *bnew bool [n];//记录数组for(int i 0;icina[i];b[i]true;}coutsystem(pause);return 0;}想了挺久的这道题幸好最后还是自己做出来了。。
