欧酷网

您的位置:主页>算法>

洛谷p1094纪念品分组-贪心算法

https://www.luogu.com.cn/problem/P1094


一组最多两件纪念品,那么一般小的纪念品都能凑成一对满足要求,但是大的纪念品就只能单独作为一组了,这无疑会增加组数,所以尽量为大的纪念品找小的纪念品凑成一对,这样最终一定会得到最优解

#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <vector>#include <string>#include <queue>#include <iomanip>using namespace std;#define MAX 30005int arr[MAX];int t[MAX];int main() {#ifdef ONLINE_JUDGE#else
	freopen("1.txt", "r", stdin);#endif // ONLINE_JUDGE
	int n, w, num = 1, sum = 0;
	cin >> w >> n; 
	for (int i = 0; i < n; i++)cin >> arr[i];
	sort(arr, arr + n);
	int l = 0, r = n - 1;
	while (l <= r) {
		if (arr[l] + arr[r] <= w)
			l++, r--, sum++;
		else
			r--, sum++;
	}
	cout << sum << endl;}

相关文章推荐