- 原題：https://onlinejudge.org/external/101/10154.pdf
- 中文：https://zerojudge.tw/ShowProblem?problemid=f347

:::spoiler Solve Key
- Moore–Hodgson Algorithm
- priority queue
:::

## 題解
這題直觀的想法是讓越會扛的在下面，但是想了一下，然後一隻一隻往上疊，
因此在想到應該可以用 Greedy 解的同時也大概想到是 Moore-Hodgson Algorithm，
但是如果第 i 層扛得住第 i+1 層可是第 i+1 層卻扛不住第 i+2 層的話，那我要怎麼維護？

後來想到那我乾脆變成讓力量最小的在最上面，由上往下排，
同時記錄現在的累加總重，如果當前該隻烏龜扛不住那就把目前最重的那隻給踢出去。

## 程式碼

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define pii pair<int, int>
#define x first
#define y second
#define fastio ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

int p, q, sum;
vector<pii> vec;
priority_queue<int> pq;

bool cmp(pii a, pii b) {
	if(a.y==b.y) return a.x < b.x;
	return a.y < b.y;
}

signed main() {
	fastio
	while(cin >> p >> q) {
		vec.push_back({p, q});
	}
	sort(vec.begin(), vec.end(), cmp);
	for(int i=0; i<vec.size(); i++) {
		
		pq.push(vec[i].x);
		sum += vec[i].x;
		if(sum > vec[i].y) {
			sum -= pq.top();
			pq.pop();
		}
	}
	cout << pq.size() << '\n';
	return 0;
}

## 補充
- DP解：https://nicknick0630.github.io/2019/03/07/UVa-10154-Weights-and-Measures/

###### tags: `Algorithm` `詳解`
{%hackmd /iXnHuqXjTCKhrH2YVqT5AQ?both %}