POI 1997 獨木舟 Canoes
本文正體字版由OpenCC轉換
居然看到有人寫的是一般圖的最大匹配，其實排序就行了。設定兩個遊標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