可以使用Minimizing Tardy Jobs的技巧
(把烏龜所能乘載的最大重量(carry)當作Due date, 烏龜的重量當作processing time.)
(有興趣可以參考我之前的文章 Single Machine Scheduling - Minimizing Number of Tardy Jobs)
概念是將烏龜從頂端開始往下放，因為越下面的乘載量應該要越大，所以將烏龜依照carry能力由小排到大。(carry = strength - weight)
原理基本上就是因為烏龜已經依照承載量排序，如果原本最底下的烏龜可以承受整個重量，那麼最新的烏龜一定也可以取代最底下的烏龜承受整個重量（越後面的烏龜能力越好）。而且由於當我們在挑最新的烏龜的時候，是先將最新的烏龜放到最底下，所以暫時不用考慮他的重量是不是會導致整個重量太重（會在之後放新的烏龜時考慮）。
所以如果新的烏龜撐得住全部，那麼就直接加入(Size++)。
如果不行，那麼再從中把最重的烏龜踢掉。也就是新的烏龜一定放的進來（能力比較好），那麼我們就整個stack當中踢掉最重的烏龜，然後補這隻烏龜進來。整個Stack少了最重的烏龜，加了新的烏龜，Size不變，但總重變輕 -> 有優化的趨勢，算一種greedy method.
整個步驟大概是：
- 將烏龜依照carry能力排序
- 創立一個stack來存放堆疊的烏龜
- 依照順序將烏龜放入stack （每一次都要更新總重量）
- 如果新的烏龜的乘載量大於目前的總重量，就將他直接放入。如果新的烏龜的乘載量小於目前的總重量，就找出目前堆疊中最重的烏龜，把他移除。（注意！因為我們要盡可能讓stack的總重輕一點，找最重的烏龜的時候要包含這隻最新的烏龜，所以實作時建議先放入再挑出烏龜。）
// main.cpp
// UVA_10154_Weight_and_Measure
//
// Created by Darklanx on 2018/1/31.
// Copyright © 2018年 Darklanx. All rights reserved.
//
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct Turtle{
int weight, carry;
Turtle(int w, int strength){
weight = w;
carry = strength - weight;
}
};
bool sort_by_carry_asc(Turtle t1, Turtle t2){
return t1.carry < t2.carry;
}
vector<Turtle>::iterator find_heaviest(vector<Turtle>& turtles){
vector<Turtle>::iterator fat_turtle;
int max =0;
for(vector<Turtle>::iterator it=turtles.begin();it!=turtles.end();it++){
if(it->weight > max){
max = it->weight;
fat_turtle = it;
}
}
return fat_turtle;
}
//sort by (strength - weight) in ascending order
//start adding turtles (Top-down)
//if: (strength >= total_weight) add that damn turtle (stack++)
//else: find the heaviest turtle, kick him out(stack+=0)
int main() {
int iweight, istrength;
//int max_stack =0;
vector<Turtle> turtles;
vector<Turtle>::iterator it;
//vector it
//input turtles
while(cin >> iweight >> istrength){
Turtle t(iweight,istrength);
turtles.push_back(t);
}
//sort
sort(turtles.begin(),turtles.end(),sort_by_carry_asc);
int total_weight=0;
it = turtles.begin();
vector<Turtle> stacking;
while(it != turtles.end()){
//!!!!
//一定要先把最新的烏龜推進去 假設最新的烏龜是最重的烏龜 下面再移除的時候才有辦法把它移除
stacking.push_back(*it);
if(it->carry >= total_weight){// if can carry
//max_stack ++;
total_weight += it -> weight;
}else{// too heavy
//remove the heaviest
total_weight -= find_heaviest(stacking) -> weight;
stacking.erase(find_heaviest(stacking));
total_weight += it -> weight;
}
it++;
}
cout << stacking.size() << endl;
return 0;
}
