1557-B, *1100

Problem - 1557B - Codeforces

문제

• 중복된 원소가 없는 크기가 $n(1 \leq n \leq 10^{5})$인 배열이 주어진다
• 이 배열을 $k$개의 조각으로 나누어 오른차순으로 sort 할 수 있는가?

 

$O(nlog\ n)$

먼저 각 원소의 상대적인 크기 비교하여 $1$부터 $n$으로 indexing 하자 $O(nlog\ n)$

origin	3	-1	6	2
substitute	3	1	4	2

 

이제 오름차순으로 정렬되기 위한 최소 조각의 개수를 구하자
위와 같이 치환하여 생각할 때,
$$\mathrm{array[i] \neq array[i-1]+1}$$
이면 $\mathrm{array[i]}$와 $\mathrm{array[i-1]}$는 다른조각이어야 한다 $O(n)$

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int n, k;
int a[100001] {};
int b[100001] {};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n >> k;
        loop(i, n){
            cin >> a[i];
            b[i] = a[i];
        }
 
        sort(b+1, b+1+n);
 
        map<int, int> m;
        loop(i, n) m[b[i]] = i;
        loop(i, n) a[i] = m[a[i]];
 
        int boundary = n;
        for(int i = 2; i <= n; i++){
            if(a[i] == a[i-1]+1) boundary--;
        }
 
        cout << ((boundary <= k)? "Yes": "No") << endl;
 
    }
 
    return 0;
}cs

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int n, k;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n >> k;
        vector<pair<int, int> > v(n);
        for(int i = 0; i < n; i++){
            cin >> v[i].first;
            v[i].second = i;
        }
 
        sort(v.begin(), v.end());
 
        int boundary = 1;
        for(int i = 1; i < n; i++){
            if(v[i].second != v[i-1].second + 1) boundary++;
        }
 
        cout << ((k >= boundary)? "Yes": "No") << endl;
 
    }
 
    return 0;
}cs