POI 1997 独木舟 Canoes
居然看到有人写的是一般图的最大匹配，其实排序就行了。设定两个游标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
上次修改时间 2017-02-03