題意 ：

• 給一01序列，要求若干次操作后序列整體非嚴格遞增，每次操作可以選一個非嚴格遞減的子序列發(fā)生逆序，求最小操作次數(shù)

思路 ：

• 非嚴格遞增，要變成000…0111…1的形式
• 定義cnt為1的個數(shù)，找出最后cnt個數(shù)中0的下標和，前n-cnt個數(shù)中的1的下標，然后1次操作，既可以讓序列整體非嚴格遞增，又滿足了非嚴格遞減的子序列，而且是最小操作次數(shù)。找出所有所需下標后還要忘了排序
• 特殊地，如果原序列就是00…011…1的形式，最小操作次數(shù)為0

#include <iostream> #include <algorithm> #include <vector> #define pb push_backusing namespace std;const int N = 1010;int a[N], b[N];int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int _;cin >> _;while (_ -- ){int n;cin >> n;string s;cin >> s;for (int i = 1; i <= n; i ++ ) a[i] = s[i - 1] - '0', b[i] = a[i];sort(b + 1, b + 1 + n);bool flag = true;for (int i = 1; i <= n; i ++ )if (a[i] != b[i]){flag = false;break;}if (flag){cout << 0 << endl;continue;}cout << 1 << endl;vector<int> ve;int cnt = 0;for (int i = 1; i <= n; i ++ ) cnt += (a[i] == 1);for (int i = n; i >= n - cnt + 1; i -- )if (a[i] == 0)ve.pb(i);for (int i = 1; i <= n - cnt; i ++ )if (a[i] == 1)ve.pb(i);sort(ve.begin(), ve.end());cout << ve.size() << ' ';for (auto it : ve) cout << it << ' ';cout << endl;}return 0; }

總結

以上是生活随笔為你收集整理的Reverse Sort 思维的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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