A.Wonderful Permutation
题目描述
God's Blessing on This PermutationForces!
A Random Pebble
You are given a permutation p_1,p_2,\ldots,p_n 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 p_i with p_j .
Find the minimum number of operations needed to make the sum p_1 + p_2 + \ldots + p_k 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 p_1,p_2,\ldots,p_n ( 1 ≤ p_i ≤ 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 p_1 + p_2 + \ldots + p_k 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
1
0
2
0
提示
In the first test case, the value of p_1 + p_2 + \ldots + p_k is initially equal to 2 , but the smallest possible value is 1 . You can achieve it by swapping p_1 with p_3 , resulting in the permutation [1, 3, 2] .
In the second test case, the sum is already as small as possible, so the answer is 0 .
题意
给你一串由1-n组成的数组（长度为n）,和一个≤n的数k。
要求你替换p[1] - p[k]之间的数，使得p[1] 到 p[k]的和最小
思路
我们可以知道在该数组中只有1到n组成，并且没有重复的，因此，要是前k个数的和最小，就要保证前k个数都是小于等于k的。
这样，我们就可以从k+1开始寻找，如果这个数大于k，ans++
C++代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 110;
int n , k;
int p[N];
void solve()
{
cin >> n >> k;
for(int i = 1;i <= n;i ++)
cin >> p[i];
int ans = 0;
for(int i = k + 1;i <= n;i ++)
{
if(p[i] <= k)
ans ++;
}
cout << ans << endl;
}
int main()
{
int T;
cin >> T;
while(T --) solve();
return 0;
}
B.Woeful Permutation
题目描述
I wonder, does the falling rain
Forever yearn for it's disdain?
Effluvium of the Mind
You are given a positive integer n .
Find any permutation p of length n such that the sum \operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n) is as large as possible.
Here \operatorname{lcm}(x, y) denotes the least common multiple (LCM) of integers x and y .
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 ≤ 1\,000 ). Description of the test cases follows.
The only line for each test case contains a single integer n ( 1 ≤ n ≤ 10^5 ).
It is guaranteed that the sum of n over all test cases does not exceed 10^5 .
输出格式
For each test case print n integers p_1 , p_2 , \ldots , p_n — the permutation with the maximum possible value of \operatorname{lcm}(1,p_1) + \operatorname{lcm}(2, p_2) + \ldots + \operatorname{lcm}(n, p_n) .
If there are multiple answers, print any of them.
样例 #1
样例输入 #1
2
1
2
样例输出 #1
1
2 1
提示
For n = 1 , there is only one permutation, so the answer is [1] .
For n = 2 , there are two permutations:
[1, 2]— the sum is\operatorname{lcm}(1,1) + \operatorname{lcm}(2, 2) = 1 + 2 = 3.[2, 1]— the sum is\operatorname{lcm}(1,2) + \operatorname{lcm}(2, 1) = 2 + 2 = 4.
题意
给你一个n，要求你创建一个有1到n组成的数组，该数组中，没有元素相等，并且要求该数组的lcm(1,p1) + lcm(2,p2) + ... + lcm(n,pn)最大
思路
我们不难发现，lcm(i,p[i-1]) + lcm(i-1,p[i])最大
因此：
- 如果n为偶数时，刚好可以两两一组交换
- 如果n为奇数时，我们将p[1]匹配1，剩下的元素两两一组
C++代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int p[N];
void solve()
{
cin >> n ;
for(int i = n;i >= 2;i -= 2)
{
p[i] = i - 1;
p[i - 1] = i;
}
if(n % 2 == 1)//奇数的话，第一项会漏掉
p[1] = 1;
for(int i = 1;i <= n;i ++)
cout << p[i] << " ";
cout << endl;
}
int main()
{
int T;
cin >> T;
while(T --) solve();
return 0;
}
C.Sort Zero
题目描述
An array is sorted if it has no inversions
A Young Boy
You are given an array of n positive integers a_1,a_2,\ldots,a_n .
In one operation you do the following:
- Choose any integer
x. - For all
isuch thata_i = x, doa_i := 0(assign0toa_i).
Find the minimum number of operations required to sort the array in non-decreasing order.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1 ≤ t ≤ 10^4 ). Description of the test cases follows.
The first line of each test case contains a single integer n ( 1 ≤ n ≤ 10^5 ).
The second line of each test case contains n positive integers a_1,a_2,\ldots,a_n ( 1 ≤ a_i ≤ n ).
It is guaranteed that the sum of n over all test cases does not exceed 10^5 .
输出格式
For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order.
样例 #1
样例输入 #1
5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1
样例输出 #1
1
2
4
3
0
提示
In the first test case, you can choose x = 3 for the operation, the resulting array is [0, 0, 2] .
In the second test case, you can choose x = 1 for the first operation and x = 3 for the second operation, the resulting array is [0, 0, 0, 0] .
题意
给你一个长度为n的数组a，每一次可以进行一个操作：选择一个数x,将数组a中所有等于x的数变为0，求将这个数组变成不下降序列，最少需要操作多少次？
思路
我们用set容器维护1~i值的个数，如果出现a[i] > a[i+1]，那么就将1~i中的所有值标为0，答案更新为1 ~ i中值的个数
C++代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
const int N = 1e5+10;
int n;
int a[N] ;
bool st[N];
void solve()
{
cin >> n;
for(int i = 1;i <= n;i ++)
cin >> a[i];
memset(st,false,sizeof st);
set<int> s;
int ans = 0,last = 0;
for(int i = 1;i < n;i ++)
{
if(st[ a[i] ] == true)
a[i] = 0;
if(st[ a[i + 1] ] == true)
a[i + 1] = 0;
if(a[ i ] != 0)
s.insert(a[i]);
if(a[ i ] > a[i + 1])
{
for(int j = last;j <= i;j ++)
st[ a[j] ] = true;
last = i;
ans = s.size();
}
}
// cout << "Ans = ";
cout << ans << endl;
}
int main()
{
int T;
cin >> T;
while(T --) solve();
return 0;
}