目录
1.排序子序列
2.消减整数
3.最长上升子序列(二)
1.排序子序列
链接
https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471
利用指针模拟即可，注意过渡掉开头的恒定段即可。
#include <iostream>
using namespace std;
const int N = 1e5 + 10;int a[N];
int n;
int main() {cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];int i = 1;int ret = 0;while (i <= n){if (i == n){ret++;break;}if (a[i] < a[i + 1]){ret++;while (i + 1 <= n && a[i] <= a[i + 1]){i++;}}else if (a[i] > a[i + 1]){ret++;while (i + 1 <= n && a[i] >= a[i + 1]){i++;}}else{while (i + 1 <= n && a[i] == a[i + 1]){i++;}}++i;}cout << ret << endl;return 0;
}2.消减整数
链接https://ac.nowcoder.com/acm/problem/219038
数学规律加上一点贪心（本质就是不能一味的贪心，因为题意要求恰好减为0）
#include <iostream>
using namespace std;int t, h;
int solve()
{if(h == 1)return 1;int ret = 0;int a = 1;while(h){h -= a;ret++;if(h % (2 * a) == 0)a *= 2;}return ret;
}int main()
{cin >> t;while(t--){cin >> h;cout << solve() << endl;} return 0;
}3.最长上升子序列(二)
链接https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237?tpId=196&tqId=39285&ru=/exam/oj
class Solution
{int dp[100010] = { 0 }; // dp[i] 表⽰：⻓度为 i 的最⼩末尾int pos = 0;
public:int LIS(vector<int>& a){for (auto x : a){// 查找 x 应该放在哪个位置if (pos == 0 || x > dp[pos]){dp[++pos] = x;}else{// ⼆分查找插⼊位置int l = 1, r = pos;while (l < r){int mid = (l + r) / 2;if (dp[mid] >= x) r = mid;else l = mid + 1;}dp[l] = x;}}return pos;}
};
