Problem - 1712A - Codeforces
codeforces.com
최대 최소 Swap
- 제목
Wonderful Permutation
- 조건
time limit per test : 1 second
memory limit per test : 256 megabytes
input : standard input
output : standard output
- 문제
You are given a permutation p1,p2,…,pn of length n and a positive integer k≤n.
In one operation you can choose two indices i and j (1≤i<j≤n) and swap pi with pj.
Find the minimum number of operations needed to make the sum p1+p2+…+pk as small as possible.
A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).
- 입력
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). Description of the test cases follows.
The first line of each test case contains two integers n and k (1≤k≤n≤100).
The second line of each test case contains n integers p1,p2,…,pn (1≤pi≤n). It is guaranteed that the given numbers form a permutation of length n.
- 출력
For each test case print one integer — the minimum number of operations needed to make the sum p1+p2+…+pk as small as possible.
| 예제 입력1 | 예제 출력1 |
| 4 3 1 2 3 1 3 3 1 2 3 4 2 3 4 1 2 1 1 1 |
1 0 2 0 |
#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc, sz, k;
cin >> tc;
while(tc--){
cin >> sz >> k;
int *arr = new int[sz];
for(int n = 0 ; n < sz ; n++) cin >> arr[n];
if(k != 1) sort(arr, arr + k);
if(k != sz) sort(arr + k, arr + sz);
int cnt = 0;
if(k > sz - k){
for(int n = k, m = k - 1 ; n < sz ; n++, m--){
if(arr[n] < arr[m]) {
swap(arr[n], arr[m]);
cnt++;
}
}
}
else{
for(int n = k - 1, m = k; n >= 0 ; n--, m++){
if(arr[n] > arr[m]) {
swap(arr[n], arr[m]);
cnt++;
}
}
}
cout << cnt << endl;
}
return 0;
}