71-独木舟上的旅行

题目描述:

进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。一条独木舟最多只能乘坐两个人，且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则，计算要安置所有旅客必须的最少的独木舟条数，并输出结果。

输入描述:

第一行输入s,表示测试数据的组数；

每组数据的第一行包括两个整数w，n，80<=w<=200,1<=n<=300，w为一条独木舟的最大承载量,n为人数；

接下来的一组数据为每个人的重量（不能大于船的承载量）；

输出描述:

每组人数所需要的最少独木舟的条数。

样例输入:

复制

3

85 6

5 84 85 80 84 83

90 3

90 45 60

100 5

50 50 90 40 60

样例输出:

5

3

3

分析：
　　1、排完序后，从两边开始向中间贪心；
　　2、两端之和小于总重，两端共同向中心靠近一步，否则就是大的那点向中心靠近
　　PS:输入、输出要注意数据类型

核心代码：

 while(i <= j)

 {

     if(A[i] + A[j] <= max_weight)

     {

         ++ i, -- j;

         ++ cnt;

     }

     else

     {

         ++ i;

         ++ cnt;

     }

 }

C/C++代码实现（AC）:

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <stack>

 #include <map>

 #include <queue>

 #include <set>

 using namespace std;

 const int MAXN = ;

 int A[MAXN];

 int main()

 {

     int t;

     scanf("%d", &t);

     while(t --)

     {

         int max_weight, n, cnt = , i = , j;

         scanf("%d%d", &max_weight, &n);

         for(int i = ; i < n; ++ i)

             scanf("%d", &A[i]);

         sort(A, A+n,greater<int>());

         j = n-;

         while(i <= j)

         {

             if(A[i] + A[j] <= max_weight)

             {

                 ++ i, -- j;

                 ++ cnt;

             }

             else

             {

                 ++ i;

                 ++ cnt;

             }

         }

         printf("%d\n", cnt);

     }

     return ;

 }

巴特西

nyoj 71-独木舟上的旅行(贪心)

71-独木舟上的旅行

题目描述:

输入描述:

输出描述:

样例输入:

样例输出:

最新文章

热门文章