B. Quick Sort【Codeforces Round #842 (Div. 2)】
B. Quick Sort
You are given a permutation【排列】† \(p\) of length \(n\) and a positive integer \(k≤n\).
In one operation, you:
Choose \(k\) distinct elements【不连续的元素】 \(p_{i1},p_{i2},…,p_{ik}\).
Remove them and then add them sorted in increasing order to the end of the permutation.
For example, if \(p=[2,5,1,3,4]\) and \(k=2\) and you choose \(5\) and \(3\) as the elements for the operation, then \([2,5,1,3,4]→[2,1,4,3,5]\).
Find the minimum number of operations needed to sort the permutation in increasing order【递增次序】. It can be proven that it is always possible to do so.
† A permutation of length \(n\) 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).
Input
The first line contains a single integer \(t (1≤t≤10^4)\) — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers \(n\) and \(k (2≤n≤10^5, 1≤k≤n)\).
The second line of each test case contains \(n\) integers \(p_1,p_2,…,p_n (1≤pi≤n)\). It is guaranteed that \(p\) is a permutation.
It is guaranteed that the sum of n over all test cases does not exceed \(10^5\).
Output
For each test case output a single integer — the minimum number of operations needed to sort the permutation. It can be proven that it is always possible to do so.
Example
input
4
3 2
1 2 3
3 1
3 1 2
4 2
1 3 2 4
4 2
2 3 1 4
output
0
1
1
2
Note
In the first test case, the permutation is already sorted.
In the second test case, you can choose element \(3\), and the permutation will become sorted as follows: \([3,1,2]→[1,2,3]\).
In the third test case, you can choose elements \(3\) and \(4\), and the permutation will become sorted as follows: \([1,3,2,4]→[1,2,3,4]\).
In the fourth test case, it can be shown that it is impossible to sort the permutation in \(1\) operation. However, if you choose elements \(2\) and \(1\) in the first operation, and choose elements \(3\) and \(4\) in the second operation, the permutation will become sorted as follows: \([2,3,1,4]→[3,4,1,2]→[1,2,3,4]\).
简述题意
- 给出一个长度为\(n\)的不连续排列,通过每次移动\(k\)个数并排序放在排列的最后面,确保一定次数内一定可以使得排列正序,问最小操作数为几?
思路
- 如果需要最小化操作数,那么不需要移动的元素个数应该最大化,即找到{1,2,...}的maximal subsequence【最大子序列】的元素个数
- 我们可以在遍历过程中维护相对顺序来找到最大子序列的元素个数
- 结果是遍历一遍记录不满足相对顺序的个数除以每次可移动的个数向上取整
- 需要注意是:向上取整要先乘1.0,否则结果会先向下取整再向上取整
代码
点击查看代码
#include<iostream>
#include<cmath>
#define endl '\n'
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int k,t,n;
int a[N];
LL ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> t;
while(t -- ){
ans = 0;
cin >> n >> k;
for(int i = 1; i <= n; i ++)cin >> a[i];
int t = 0,m = 0;
for(int i = 1; i <= n; i ++){
if(a[i] != i - t){
m ++; //不满足相对顺序的数的个数
t ++; //维护相对顺序
}
}
cout << ceil(m * 1.0 / k) << endl; //注意:向上取整要先乘1.0,否则结果会先向下取整再向上取整
}
}
标准答案
点击查看代码
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n'; //简写换行
typedef long long ll;
typedef long double ld;
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> p(n); //动态数组
for (int i = 0; i < n; i++) cin >> p[i];
int c_v = 1;
for (int i = 0; i < n; i++) {
if (p[i] == c_v) c_v++;
}
cout << (n - c_v + k) / k << nl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T--) solve();
}
解题历程
- 考虑了相对顺序但是结果计算方式错误
- AC(46 ms,3900 KB) 【00:57 - 01:29】 //二次思考
经验总结
- 向上取整要先乘1.0,否则结果会先向下取整再向上取整
- 注意如何维护相对顺序
- 不要盲目模拟过程
最新文章
- ASP.NET MVC Model元数据(三)
- css的初始化样式
- Spring MVC学习笔记——引入静态文件
- 通过TStringList保存csv文件,只要循环.Add表格里面的每行记录进去,保存即可
- Js-字符串截取substring,分割split,指标indexOf,拼接John
- Entity Framework 第五篇 状态跟踪
- Merge OUTPUT 高级用法综合写的一个MergeTab的存储过程
- 7、Web应用程序中的安全向量 -- 使用Retail部署配置
- Python正则表达式,统计分析nginx访问日志
- 关于InnoDB存储引擎text和blob类型的优化
- C#使用Socket实现一个socket服务器与多个socket客户端通信
- Android Data Binding实战(一)
- 附实例!图解React的生命周期及执行顺序
- nginx配置location总结及rewrite规则写法(转)
- 性能测试二十九:Dubbo框架测试脚本编写
- Python装饰器探险
- Ubuntu16.04通过GPT挂载硬盘
- Docker关联使用的一些工具:Clip名字服务(转载)
- POJ 2289 Jamie&#39;s Contact Groups 二分图多重匹配 难度:1
- 【CS231N】6、神经网络动态部分:损失函数等