A. Wonderful Permutation
题目链接：
题面：
题意：
你可以任意选择两个位置，然后交换两个位置上的数，问：使前k个数相加最小需要交换几次
思路：
我们可以统计最小的k个数有几个的位置大于等于k即可
代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int num;
int i;
}arr[105];
bool cmp(node a, node b){
return a.num < b.num;
}
int main(){
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> arr[i].num;
arr[i].i = i;
}
sort(arr, arr + n, cmp);
int ans = 0;
for(int i = 0; i < k; i++){
if(arr[i].i >= k){
ans++;
}
}
cout << ans << endl;
}
return 0;
}B. Woeful Permutation
题目链接：
题面：
题意：
一共有n个数，需要构造一个排列p，使得sum（lcm（i， pi））最大
思路：
lcm（n， n-1）一定是所有搭配里面最大的
在区间内lcm（i， i+1）是最大的，我们只需要从大到小把两个相邻的放在一个求lcm即可
代码：
#include<bits/stdc++.h>
using namespace std;
int arr[100005];
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = n; i >= 1; i -= 2){
if(i > 1){
arr[i - 1] = i;
arr[i] = i - 1;
}else{
arr[i] = i;
}
}
for(int i = 1; i <= n; i++){
if(i != 1){
cout << " ";
}
cout << arr[i];
}
cout << endl;
}
return 0;
}C. Sort Zero
题目链接：
题面：
题意：
有一个n个数的数组，我们可以选择一个x找到所有ai == x的，并把ai变成0，问最少需要几步能把数组变成非递减数组
思路：
我们从后往前考虑，如果所有的an都是连续的，那么an就不用变成0，然后不断缩小n即可，如果an不是连续的，无论中间的数比an大还是小，我们都需要把前面所有的位置（包括n）的数变成0
代码：
#include<bits/stdc++.h>
using namespace std;
int arr[100005];
vector<int> ve[100005];
bool vis[100005];
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
ve[i].clear();
vis[i] = 0;
}
int num = 0;
for(int i = 1; i <= n; i++){
cin >> arr[i];
if(vis[arr[i]] == 0){
num++;
}
vis[arr[i]] = 1;
ve[arr[i]].push_back(i);
}
int ans = 1e5 + 5;
int cnt = 0;
for(int i = n; i >= 1; i--){
int a = arr[i];
// cout << a << " " << ans << " : ";
if(a < ans){
int m = ve[a].size() - 1;
bool f = 0;
for(int j = 1; j <= m; j++){
// cout << ve[a][m - j] << " ";
if(ve[a][m - j] != i - j){
f = 1;
break;
}
}
// cout << endl;
if(f){
break;
}
cnt++;
ans = a;
i = i - m;
}else{
break;
}
}
// cout << endl;
cout << num - cnt << endl;
}
return 0;
}