Haut OJ 1241: League activities of class XXX

Problem description ：

  The once-a-month League event has come again , This activity is an outing , But? , The League branch secretary immediately poured cold water , It is said that our destination is on an island across the sea , You need to take a canoe to get to the island , A canoe can only take two people at most , And the total weight of passengers shall not exceed the maximum carrying capacity of the canoe . And the rental of canoes is very expensive , The class fee is limited .. We should try to reduce the cost of this activity , So find out the minimum number of canoes that can accommodate all students ,ykc I really want to go on this outing , Can you write a program to help him find out the minimum number of canoes to rent ？

Input ：

First line input s, Number of groups representing test data ;
The first row of each set of data includes two integers w,n,80<=w<=200,1<=n<=300,w It is the maximum carrying capacity of a canoe ,n For the number of people ;
The next set of data is the weight of each person （ Not more than the carrying capacity of the ship ）;

Output ：

The minimum number of canoes to rent per group

The sample input ：

3
85 6
5 84 85 80 84 83
90 3
90 45 60
100 5
50 50 90 40 6

Sample output ：

5
3
3

---

Cause analysis ：

First, arrange the array from small to large , You can choose a largest and a smallest group of a boat , Notice the last if i=k, There is only one person left +1

---

Solution ：

#include<bits/stdc++.h>

using namespace std;

int  main()

{

      int a[205];

      int n,w,i,t,ans,k;

      scanf("%d",&t);

      while(t--)

      {

         ans=0;k=1;

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

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

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

             sort(a+1,a+n+1);

             for(i=n;i>=k;i--)

             {

                    if(a[i]>=w)

                    ans++;

                    else

                    {

                           while(a[i]+a[k]<=w && i>k)

                           {

                                  ans++;

                                  k++;

                                  i--;

                           }

                           if(a[i]+a[k]>w && i>k)

                           ans++;

                           if(i==k)

                           ans++;

                    }

             }

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

      }

}