b159 - NOIP2007 2.纪念品分组

🔗 前往 ZeroJudge 原題

題目描述

題目要求將一組紀念品按照價格進行分組，每組最多包含兩件，且每組價格總和不能超過給定的上限 w。目標是找到最少的分組數目。

解題思路

此題可以使用貪心演算法解決。首先，對紀念品的價格進行排序。然後，使用兩個指針，一個指向最小的價格，另一個指向最大的價格。如果兩個指針所指的價格之和小於或等於 w，則將它們分組，並將兩個指針分別向右移動。否則，只將指向最大價格的指針向左移動。重複此過程，直到兩個指針相遇。最終的分組數目就是最少的分組數目。

複雜度分析

• 時間複雜度: O(n log n) (主要來自排序)
• 空間複雜度: O(n) (主要來自儲存紀念品價格的陣列)

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int w,n;
	cin >> w >> n;
	int a[n],ans=n;
	for(int i=0;i<n;++i)
		cin >> a[i];
	sort(a,a+n);
	for(int i=0,k=n-1;i<k;--k)
		if(a[i]+a[k]<=w){
			--ans;
			++i;
		}
	cout << ans;
}