Codeforces 第 813 轮（第 2 部分）A~C

文章Codeforces Round #813 (Div. 2) A~C，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A. Wonderful Permutation

You are given a permutation p1,p2,…,pnp1,p2,…,pn of length nn and a positive integer k≤nk≤n.

In one operation you can choose two indices ii and jj (1≤i

Find the minimum number of operations needed to make the sum p1+p2+…+pkp1+p2+…+pk as small as possible.

A permutation is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (n=3n=3 but there is 44 in the array).

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1001≤t≤100). Description of the test cases follows.

The first line of each test case contains two integers nn and kk (1≤k≤n≤1001≤k≤n≤100).

The second line of each test case contains nn integers p1,p2,…,pnp1,p2,…,pn (1≤pi≤n1≤pi≤n). It is guaranteed that the given numbers form a permutation of length nn.

For each test case print one integer — the minimum number of operations needed to make the sum p1+p2+…+pkp1+p2+…+pk as small as possible.

A

You are given a permutation p1,p2,…,pnp1,p2,…,pn of length nn and a positive integer k≤nk≤n.

In one operation you can choose two indices ii and jj (1≤i

Find the minimum number of operations needed to make the sum p1+p2+…+pkp1+p2+…+pk as small as possible.

A permutation is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (n=3n=3 but there is 44 in the array).

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1001≤t≤100). Description of the test cases follows.

The first line of each test case contains two integers nn and kk (1≤k≤n≤1001≤k≤n≤100).

The second line of each test case contains nn integers p1,p2,…,pnp1,p2,…,pn (1≤pi≤n1≤pi≤n). It is guaranteed that the given numbers form a permutation of length nn.

For each test case print one integer — the minimum number of operations needed to make the sum p1+p2+…+pkp1+p2+…+pk as small as possible.

定义第k大的数为下，直接找前k个数中小于x的数即可，我写的倒是有一些麻烦。

#include#include#include#include

 B. Woeful Permutation

You are given a positive integer nn.

Find any permutation pp of length nn such that the sum lcm(1,p1)+lcm(2,p2)+…+lcm(n,pn)lcm⁡(1,p1)+lcm⁡(2,p2)+…+lcm⁡(n,pn) is as large as possible.

Here lcm(x,y)lcm⁡(x,y) denotes the least common multiple (LCM) of integers xx and yy.

A permutation is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (n=3n=3 but there is 44 in the array).

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤10001≤t≤1000). Description of the test cases follows.

The only line for each test case contains a single integer nn (1≤n≤1051≤n≤105).

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

For each test case print nn integers p1p1, p2p2, ……, pnpn — the permutation with the maximum possible value of lcm(1,p1)+lcm(2,p2)+…+lcm(n,pn)lcm⁡(1,p1)+lcm⁡(2,p2)+…+lcm⁡(n,pn).

If there are multiple answers, print any of them.

可以发现，只有每一对都是奇数和偶数想乘相加后才会是最大值，因此从小到大奇数和偶数错开排列即可。

注意n为奇数时让1与1相乘才能获得最大值

#include#include#include#include

 C. Sort Zero

You are given an array of nn positive integers a1,a2,…,ana1,a2,…,an.

In one operation you do the following:

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 tt (1≤t≤1041≤t≤104). Description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤1051≤n≤105).

The second line of each test case contains nn positive integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n).

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order.

二分答案，找到最靠后的一个数ax使得x到n满足非递减且前边全是0即可。

#include #include #include #include