居然看到有人写的是一般图的最大匹配，其实排序就行了。设定两个游标i,j，i指向最小的元素，j指向最大的元素。如果i和j指向的元素之和小于等于船的载重，那么这两个人使用一个船，否则j单独使用一个船。移动i,j，直到处理完所有的元素。

#include <iostream>

using namespace std;

int P,N,Ans;
int F[201];

void init()
{
    int i,a;
    freopen("kaj.in","r",stdin);
    freopen("kaj.out","w",stdout);
    scanf("%d%d",&P,&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d",&a);
        F[a]++;
    }
}

void solve()
{
    int i,j;
    for (i=5,j=P;;)
    {
        while (!F[i] && i<=j) i++;
        while (!F[j] && i<=j) j--;
        if (i>=j)
        {
            if (i==j)
            {
                if (i+i<=P)
                    Ans+=F[i]/2+F[i]%2;
                else
                    Ans+=F[i];
            }
            break;
        }
        if (i+j<=P)
        {
            Ans++;
            F[i]--;
            F[j]--;
        }
        else
        {
            F[j]--;
            Ans++;
        }
    }
}

int main()
{
    init();
    solve();
    cout << Ans << endl;
    return 0;
}

独木舟

我们想组织一次独木舟的旅游。独木舟可以在某个海港租借。所有的独木舟都相同，并且最多载两人。参加者的重量之和都不会超过给定的最大重量。我们的目的是想在此次旅行中付费最少。

输入

在文本文件的第一行有一个整数w, 80<=w<=200, 表示每个独木舟的最大载重重量。

在第二行有一个整数n, 1 <= n <= 30000,表示参与旅游的人数.

下面的n行每行一个整数，属于[5..w]. 表示参与者的重量。

输出

在文本文件的第一行有一个整数，表示最少租借独木舟的数目.

示例

输入

100
9
90
20
20
30
50
60
70
80
90

输出

6