題意 ：

• 給一序列，將其分為若干段，要求每一小段內(nèi)排序后整體非遞減，求最多能分為多少段

思路 ：

• 對一段內(nèi)部，必然有最大值和最小值，要讓分的段數(shù)最多，只要讓下一段的最小值大于這段的最大值，就可以多分一段
• 所以直接找每個數(shù)能接受的最大值和最小值
• 即找這個數(shù)往前的最大值，下個數(shù)往后的最小值（找時注意設(shè)立兩個哨兵）

#include <iostream> #include <algorithm> #include <cstring> #include <queue> #define debug(a) cout << #a << " = " << a << endl; #define x first #define y second using namespace std; typedef long long ll;const int N = 1e6 + 10;int n; int a[N]; int maxx[N], minn[N];int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int _ = 1; // cin >> _;while (_ -- ){cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];maxx[0] = 0;minn[n + 1] = 1e9 + 7;for (int i = 1; i <= n; i ++ )maxx[i] = max(maxx[i - 1], a[i]);for (int i = n; i >= 1; i -- )minn[i] = min(minn[i + 1], a[i]);int ans = 0;for (int i = 1; i <= n; i ++ )if (maxx[i] <= minn[i + 1])ans ++ ;cout << ans << endl;}return 0; }

• 附上另一種方案，只記錄后綴的，且不增加哨兵

#include <iostream> #include <algorithm> #include <cstring> #include <queue> #define debug(a) cout << #a << " = " << a << endl; #define x first #define y second using namespace std; typedef long long ll;const int N = 1e6 + 10;int n; int a[N]; int maxx[N], minn[N];int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int _ = 1; // cin >> _;while (_ -- ){cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];int mi = a[n];for (int i = n; i >= 1; i -- ){mi = min(mi, a[i]);minn[i] = mi;}int mx = 0, ans = 0;for (int i = 1; i <= n; i ++ ){if (mx <= minn[i]) ans ++ ;mx = max(mx, a[i]);}cout << ans << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Kobolds and Catacombs 思维，模拟，前缀，后缀（沈阳）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。