UVa1260 - Sales(LIS)

題目大意：

有一家公司希望可以看今天的銷售金額比哪幾天高、等於，輸出哪幾天高的總和，如果前幾天是 \(20,30,40\)，那 30 那天的銷售金額就比前一天高，輸出 1；如果是 40 那天的銷售金額就輸出 2，大於前兩天的銷售金額，請輸出總和所有的銷售金額比哪些天高的天數並減一。

題目連結

重點觀念

• 了解並學會 LIS
• 實踐 LIS
• 演算法知識 - Longest Increasing Subsequence 最長遞增子序列(時間複雜度 O(nlogn))

分析：

這題就是簡單的 LIS，相信大家在看 uva 的題目時就能馬上知道這是 LIS，只需要學會 LIS 就能解出此題，但需要注意的是這題在相等時也要算入總和內，因此不可以使用 lower_bound 改使用 upper_bound 會更好！

參考來源

演算法知識 - Longest Increasing Subsequence 最長遞增子序列(時間複雜度 O(nlogn))
演算法筆記 - Longest Increasing Subsequence

心得

原本都是用比較麻煩的方式來寫，在師大的演算法筆記中發現了更棒的寫法，因此現在改用這種寫法認為會比之前更好寫!

也謝謝師大演算法可以讓我寫得更輕鬆如意，透過網路上教會我，是我網路上的老師！

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define MAXN 5020
#define LOCAL
using namespace std;

int a[MAXN];
int T, n, len = 0, cur;


int lis(){
    deque<int> b; //用來產生 LIS 長度
    b.push_back(a[0]); ///先放入一個數值，以避免 b.back() 找不到值
    int sz = 0, temp; //sz 為每個營收高於其它天的總和
    //temp 紀錄二分搜尋後找到的位置
    for(int i = 1; i < n; i++){
        if(a[i] > b.back()){ //如果現在這個數字大於此數列中最大的數字
            sz += b.size(); //表示今天大於其他天全部營收，直接加入 sz
            b.push_back(a[i]); //LIS push back
        }
        else{
            temp = upper_bound(b.begin(), b.end(), a[i]) - b.begin(); 
            //二分搜尋，找到他適合的位置，前面數字比她小或相等，後面數字大
            b.insert(b.begin()+temp , a[i]); //插入她
            sz += temp; //sz 加上前面比她小的那些天數，注意，不需要 -1，因為 queue index 從 0 開始
            
            //debug
            //for(auto it: b) cout << it << ' ';
            //cout << '\n';
        }
        //cout << "sz i is " << sz << '\n';
    }
    return sz;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> T;
    while(T--){
        cin >> n;
        for(int i = 0; i < n; i++) cin >> a[i]; //輸入資料
        cout << lis() << '\n';
    }

    return 0;
}