Introduction

陣列的大小往往都是固定的，如果你需要一個可以增減的陣列，你可能會想到std::vector。然而，既然官方的函式庫裡面有這樣的東西，就表示我們可以做一個出來。

Vector

核心概念：倍增法

當空間不足時，新增一倍的空間。也可以當作是空間\(\times 2\)。

P1 Vector

Vector.h

struct Vector {
    Vector(int _sz = 0) : sz(_sz), capacity(_sz) {
        if (sz != 0) value = new int[sz];
        else value = nullptr;
    }
    ~Vector() {
        if (value != nullptr) delete [] value;
    }
    Vector& resize(int new_size);
    Vector& push_back(int val);
    Vector& pop_back();
    int& operator[](int index) { return value[index];}
    int *value;
    int sz, capacity;
};

請完成Vector.cpp的實作。

編譯

Windows請執行.\compile.bat，Linux或Mac或WSL請使用./compile.sh。

執行

Windows請執行.\main.exe，Linux或Mac或WSL請使用./main。

應用

即便我們知道有函式庫可以用，倍增法依舊是一個很有用的技巧。

P2 睿璿的煩惱

題目敘述

睿璿學長很喜歡一個射擊遊戲，其中有許多難度不同的極限挑戰，皆由數以萬計的關卡組成。玩家要在不死亡的前提下通過所有關卡，且同一組挑戰內通過關卡並不會回復至初始血量，並且玩家可以攜帶限定數量以下(含)的大型生命補給與彈藥儲轉箱，分別可以將生命值與備彈補充至全滿。睿璿學長已經練習到可以百發百中，且通過一關僅需要一分鐘。然而他發現他的等級並不一定足夠通過所有關卡。請你幫幫他。

輸入說明

第一行有\(3\)個數字 \(n,hl,al\)，分別代表關卡數，大型生命補給與彈藥儲轉箱的使用上限

第二行有\(n\)個數字 \(amo_1,amo_2…amo_n\)，代表各個關卡需要消耗的子彈數目

第三行有\(n\)個數字 \(hpc_1,hpc_2…hpc_n\)，代表各個關卡需要消耗的生命值

第四行有\(4\)個數字 \(a,b,c,d\)，分別代表等級與生命值上限/攜帶彈藥上限的關係，如右式 \(ax+b, cx+d\)。

最後一行有兩個數字 \(LvT,lv\)，分別代表每升一級所需的時間(單位：分鐘)和他現在的等級。

輸出說明

請輸出一行 \(t\)，表示最少花費的時間。

測資規模

\(n \leq 10^5\)
\(hl,al \leq 25\)
\(1 \leq a,b,c,d \leq 10\)
\(amo_{i}\) \(,\) \(hpc_{i}\leq 10^5\)
\(0 \leq t,lv \leq 10\)

範例輸入

範例輸出

1 100

想法

因為不知道需要多少等級，所以可以利用倍增法加上二分搜。

mtmatt.Page

Dynamic Array