UVA 10154 Weight and Measure (Top-Down)

這題的概念是想辦法找出可以堆疊的最大烏龜數
可以使用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.

整個步驟大概是：

1. 將烏龜依照carry能力排序
2. 創立一個stack來存放堆疊的烏龜
3. 依照順序將烏龜放入stack （每一次都要更新總重量）
4. 如果新的烏龜的乘載量大於目前的總重量，就將他直接放入。如果新的烏龜的乘載量小於目前的總重量，就找出目前堆疊中最重的烏龜，把他移除。（注意！因為我們要盡可能讓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;
}