居然看到有人寫的是一般圖的最大匹配，其實排序就行了。設定兩個遊標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