1351: 独木舟上的旅行发表时间:2022-10-28 23:23 1351: 独木舟上的旅行 时间限制: 1 Sec 内存限制: 128 MB 题目描述 进行一次独木舟的旅行活动,独木舟可以在港口租到,并且之间没有区别。一条独木舟最多只能乘坐两个人,且乘客的总重量不能超过独木舟的最大承载量。我们要尽 量减少这次活动中的花销,所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序,读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给 出的规则,计算要安置所有旅客必须的最少的独木舟条数,并输出结果。 输入 第一行输入s,表示测试数据的组数; 输出 每组人数所需要的最少独木舟的条数。 样例输入 Copy 3 85 6 5 84 85 80 84 83 90 3 90 45 60 100 5 50 50 90 40 60 样例输出 Copy 5 3 3
解析: 每艘船上只能做两个人。我们考虑一些问题。 如果一个人的重量超过了w,是不是题目无解? 一艘船上是不是最好做2个人。 我们用贪心算法。 每次扫描剩下最重和最轻的人,如果两个人能挤到一艘船上,就把两个人塞进去;如果两个人不行,说明最重的人和任何人都不能上同一条船,因此最重的人只能单独一条船。这样一个个扫描过去。
#include<bits/stdc++.h> using namespace std; int main(){ int s; scanf("%d",&s); while(s--){ int w,n; scanf("%d%d",&w,&n); int a[305]; for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); int i=1,j=n,ans=0; while(i<=j){ if(i==j){ans++;break;} if(a[i]+a[j]<=w){ ans++;j--;i++; } else if(a[i]*2<=w){ans++;j--;} else{ans+=j-i+1;break;} } printf("%d\n",ans); } return 0; } 下一篇1353: 背包问题
文章分类:
算法例题
|