【題目敘述】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