【題解】ZeroJudge b159: NOIP2007 2.纪念品分组

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b159
【解題想法】排序,二分搜

  • w:每組紀念品(最多兩件)價格總和的上限。
  • 將 n 件紀念品的價格由小到大進行排序。
  • 每次檢查價格最大和最小的兩件紀念品的價格和是否會超過 w。
    • 如果沒有超過 w,取出價格最大和最小的兩件紀念品,湊成一組。
    • 如果超過 w,只取價格最大的紀念品,自成一組。
    • 重複此步驟。
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
	int w, n;
	while (cin >> w >> n){
		int a[n];
		for (int i=0; i<n; i++){
			cin >> a[i];
		}
		sort(a, a+n);
		int cnt = 0;
		int l = 0;
		int r = n-1;
		while (l < r){
			if (a[r] + a[l] <= w){
				l++;
				r--;
			} else {
				r--;
			}
			cnt++;
		}
		if (l == r) cnt++;
		cout << cnt << '\n';
	}
    
    return 0;
}

Python code (credit: Amy Chou)

while True:
	try:
		w = int(input())
		n = int(input())
		a = []
		for i in range(n):
			a.append(int(input()))
			
		a.sort()
		cnt = 0
		l = 0
		r = n-1
		while (l < r):
			if a[l]+a[r] <= w:
				l += 1
				r -= 1
			else:
				r -= 1
			cnt += 1
		
		if (l == r):
			cnt += 1
			
		print(cnt)
	except:
		break
分享本文 Share with friends