【今日三题】排序子序列(模拟) / 消减整数(贪心) / 最长上升子序列(二)(贪心+二分)

#include <iostream>
using namespace std;

const int N = 1e5 + 1;
int n, arr[N], res;

int main() 
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    int i = 0;
    while (i < n)
    {
        if (i == n - 1) 
        {
            res++;
            break;
        }
        if (arr[i] > arr[i + 1])
        {
            while (i + 1 < n && arr[i] >= arr[i + 1]) i++;
            res++;
        }
        else if (arr[i] < arr[i + 1])
        {
            while (i + 1 < n && arr[i] <= arr[i + 1]) i++;
            res++;
        }
        else 
        {
            while (i + 1 < n && arr[i] == arr[i + 1]) i++;
        }
        i++;
    }
    cout << res << endl;
    return 0;
}

#include <iostream>
using namespace std;

int t, h;

int main()
{
    cin >> t;
    while (t--)
    {
        int h = 0, cnt = 0, a = 1;
        cin >> h;
        while (h)
        {
            cnt++;
            h -= a;
            if (h % (2 * a) == 0) a *= 2;
        }
        cout << cnt << endl;
    }
    return 0;
}

class Solution {
public:
    int LIS(vector<int>& a) {
        if (a.empty()) return 0;
        vector<int> v;
        v.push_back(a[0]);
        for (int i = 1; i < a.size(); i++)
        {
            if (a[i] > v.back()) v.push_back(a[i]);
            else
            {
                int l = 0, r = v.size() - 1;
                while (l < r)
                {
                    int mid = l + (r - l) / 2;
                    if (a[i] > v[mid]) l = mid + 1;
                    else r = mid;
                }
                v[r] = a[i];
            }
        }
        return v.size();
    }
};