[数据结构与算法]【CF1557B】Moamen and k-subarrays

传送门

我的想法

以为只用统计连续多少段递增的序列就是最少需要的分类数

my Code

//
// Created by 009 on 2022/3/8.
//

#include<bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        vector<int> v(n);
        for(int i = 0; i < n; i++) cin >> v[i];
        int count = 1;
        int pre = v[0];
        // 记录分段有多少个subarray是连续的
        for(int i = 1; i < n; i++) {
            if(pre > v[i]) count += 1;
            pre = v[i];
        }
        //cout << count << endl;
        if(count > k) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
}

结果并不是这样子的
确实不行，因为中间的有序会涉及到交叉的部分，凉凉

正确analysis

需要先来一个辅助数组然后从小到大排序，然后记录原数组的value和index的map
遍历辅助数组找到原数组的位置，看看它后面紧跟着的是不是有序数组的下一个
若是的话可以继续往下
否则遍历辅助数组的下一个

ac code

//
// Created by 009 on 2022/3/8.
//

#include<bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        // 补充最后一个位置，以防越界
        vector<int> v(n), copy(n);
        map<int, int> mp; // 记录原vector中value和index的关系
        for(int i = 0; i < n; i++) cin >> v[i], copy[i] = v[i], mp[v[i]] = i;
        // 对copy sort的一下
        sort(copy.begin(), copy.end());
        int count = 0;
        // 记录原分段中有多少个满足copy排好的位置
        for(int i = 0; i < n; i++) {
            count++;
            //找到原位置，看看后面有几个接的上
            //保证j + 1不越界
            for(int j = mp[copy[i]]; j < n - 1; j++) {
                // 若连续则继续往后
                if(copy[i + 1] == v[j + 1]) i++;
                // 否则继续遍历copy
                else break;
            }
        }
        //cout << count << endl;
        if(count > k) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
}

总结

greedy + sorting
注意index的边界处理，小心越界
要知道是谁越界