A-第k小数
这个题目有很多种做法（如果题目数据不大，卡的不死的话）
- 一个是直接排序然后拿出第K个就好了，直接用sort。（O(nlogn)，最慢的）
- 一个是用STL的n_element函数，这个函数会将第k大元素放到第k个位置上。不会完全排序，所以快。
- 还有一个就是选择性快排，在选择上优化，不用快排的地方就不排了。
上面两个直接用STL函数的就不说了，就来讲一下快排做法：
- 首先快排我们都知道，就是选取一个中间值mid，将比mid小的元素放在一边，比mid大的放在另一边。
- 如果我们完全排序就和排序一样，没有区别了。那我上面说的选择上优化是什么意思呢？
- 其实简单来说：在排序后，我们已经能确定，mid的左右一边小一边大。我们按升序来说（左边小右边大）。
那么现在有第k小数，k的值比mid的数组位置还大，说明k在数组的位置一定在mid后面。 - 栗子：有100个数，我们已知当前mid在数组的第40个位置，我们现在求第44小的数，那mid一定在当前右边的区间里面。
- 那么我们已经知道k在哪边之后，另外一边就不用管了对吧（毕竟我们又不用排序，乱就乱呗）。
- 这就是我们的选择优化。
算法操作：
- 相比于正常的快排：
void quickSort(int info[], int l, int r) { int i = l, j = r, mid = info[l + r >> 1]; while (i <= j) { while (info[i] < mid) i++; while (mid < info[j]) j--; if (i <= j) { swap(info[i], info[j]); i++, j--; } } quickSort(info, l, j); quickSort(info, i, r); } - 我们只要在排序时加上特判就好了：
if (l <= j && rk <= j - l + 1) quickselect(info, l, j, rk); //rk比中值小，快排左边，在左边依旧是第k小 if (i <= r && rk >= i - l + 1) quickselect(info, i, r, rk - (i - l)); //rk比中值大，快排右边，rk在右边的区间并不是第k小，而是第rk - (i - l)小
打代码：
- STL的直接套函数就行了。
- 快排的就先输入数据。
- 然后快排呗，看上面。
- 下面代码嘞~
AC代码（sort排序）
#include <iostream>
#include <algorithm>
using namespace std;
//代码预处理区
const int MAX = 5e6 + 7;
int a[MAX];
//全局变量区
inline int read();
//函数预定义区
int main() {
int T = read();
while (T--) {
int n = read(), k = read();
for (int i = 1; i <= n; i++) a[i] = read();
sort(a + 1, a + 1 + n);
printf("%d\n", a[k]);
}
return 0;
}
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
//函数区
AC代码（STL-nth_element函数）
#include <iostream>
#include <algorithm>
using namespace std;
//代码预处理区
const int MAX = 5e6 + 7;
int info[MAX];
//全局变量区
template<class T> inline void read(T& res);
template<class T> inline void write(T res);
//函数预定义区
int main() {
int T; read(T);
while (T--) {
int n, k; read(n); read(k);
for (int i = 1; i <= n; i++) read(info[i]);
nth_element(info + 1, info + k, info + 1 + n);
write(info[k]); putchar(10);
}
return 0;
}
template<class T> inline void read(T& res) {
char c; int flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
template<class T> inline void write(T res) {
if(res < 0) {
putchar('-');
res = -res;
}
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
//函数区
AC代码（快速排序+选择优化）
#include <iostream>
using namespace std;
//代码预处理区
const int MAX = 5e6 + 7;
int info[MAX];
//全局变量区
template<class T> inline void read(T& res);//快读
template<class T> inline void write(T res);//快写
void quickselect(int info[], int l, int r, int rk);//选择快排
//函数预定义区
int main() {
int T; read(T);
while (T--) {
int n, k; read(n); read(k);
for (int i = 1; i <= n; i++) read(info[i]);
quickselect(info, 1, n, k);
write(info[k]); putchar(10);
}
return 0;
}
template<class T> inline void read(T& res) {
char c; int flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
template<class T> inline void write(T res) {
if(res < 0) {
putchar('-');
res = -res;
}
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
void quickselect(int info[], int l, int r, int rk) {
int i = l, j = r, mid = info[l + r >> 1];
while (i <= j) {
while (info[i] < mid) i++;
while (mid < info[j]) j--;
if (i <= j) {
swap(info[i], info[j]);
i++, j--;
}
}
if (l <= j && rk <= j - l + 1) quickselect(info, l, j, rk);
//rk比中值小，快排左边，在左边依旧是第k小
if (i <= r && rk >= i - l + 1) quickselect(info, i, r, rk - (i - l));
//rk比中值大，快排右边，rk在右边的区间并不是第k小，而是第rk - (i - l)小
}
//函数区
B-不平行的直线
AC代码
C-丢手绢
这道题我们可以用两种方法来写：三分法，尺取法。
- 这道题两种方法我们都讲，用的都是单峰函数的性质。理所当然的，都要用到前缀和。
首先我们还是先来看看题：
- 这道题数据有点问题，但是题目能看懂：就是告诉了你有个环，还有环的每条边长。求最远的两个点的距离。
三分法分析：
- 看到这里，我们自然的就会想到，如果是一个点去判断最远的点怎么判断呢？
很简单，遍历每个点去找从两端到达这个点的最小值中的最大值就好啦。但是这样写要O(n2)，pass。 - 然后呢我们会发现，在选取每个起点的时候我们的距离一定是先增大，后减小，我们就发现了这是一个单峰的函数：这不就是三分吗！
- 三分法就是用来找峰值的。所以对于每个点做起点，我们用三分，对于所有的起点，我们遍历一遍，所以三分时间复杂度就是O(nlogn)。
尺取法分析：
- 我们同样是发现，在选取每个起点的时候我们的距离一定是先增大，后减小。
我们就知道，要判断两端到达这个点的最小值中的最大值。
遍历过去，只要后面的距离比前面的短，不就不用判断了吗。 - 栗子：长度5的环是1,1,1,1,1。判断这个的距离 < 下一个的距离，就继续，直到判断到这个的距离 > 下一个的距离，这个时候就没必要往下走了，因为是个单峰函数，就不会再更大了。
- 然后呢，在起点向后移动的时候，现在的答案理所当然的就变小了，要增大答案只能向后移动（也就是l后移了r也必须后移才能让答案更大），这就是为什么可以用尺取。
距离计算：
- 所以接下来就是我们的距离应该怎么计算了，这里也就是我们上面说的一个很绕口的话：两端到达这个点的最小值中的最大值。
- 首先我们要知道距离怎么计算：我一开始就说了要前缀和，这个毋庸置疑。但是另一点就是这是个环，一个点到另外一个点有两条路，我们要选较短的那条。
- 所以我们就可以得出：选较短的就用min求两条路径中的较小值，而两条路的较小值就用前缀和求出来：
int dis(int u, int v) { return sum[u] - sum[v]; } int mn(int u, int v) { int len = dis(u, v); return min(len, sum[n + 1] - len); }
打代码（三分）：
- 先初始化前缀和数组。
- 然后遍历每个起点，对每个起点的情况进行三分。
- 三分的时候选出当前起点的路径最大值，并用一个ans记录这些最大值里面的最大值。
- 看代码~
打代码（尺取）：
- 先初始化前缀和数组。
- 然后开始尺取，枚举左右端点。
- 左端点随着外循环遍历而移动，右端点随着内循环计算最大值而移动。
- 再计算出并保存其中的最大值。
- 看代码~
AC代码（三分法）
#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 1e5 + 7;
int n, sum[MAX];//数据，正前缀和，反前缀和
//全局变量区
int dis(int u, int v) { return sum[u] - sum[v]; }
int mn(int u, int v) { int len = dis(u, v); return min(len, sum[n + 1] - len); }
//函数预定义区
int main() {
IOS;
cin >> n;
for (int i = 2; i <= n + 1; i++) {
cin >> sum[i];
sum[i] += sum[i - 1];
}
int ans = 0;
for (int i = 2; i <= n + 1; i++) {
int l = 1, r = n, res = 0;
while (r - l > 7) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (mn(i, mid1) < mn(i, mid2)) {
l = mid1; res = mn(i, mid2);
}
else {
r = mid2; res = mn(i, mid1);
}
//二分求最近距离
}
for (int j = l; j <= r; j++) res = max(res, mn(i, j));
//从这些剩下的里面求最远的距离
ans = max(ans, res);
}
cout << ans << endl;
return 0;
}
//函数区
AC代码（尺取法）
#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 1e5 + 7;
int n, sum[MAX];//数据，正前缀和，反前缀和
//全局变量区
int dis(int u, int v) { return sum[u] - sum[v]; }
int mn(int u, int v) { int len = dis(u, v); return min(len, sum[n + 1] - len); }
//函数预定义区
int main() {
cin >> n;
for (int i = 2; i <= n + 1; i++) {
cin >> sum[i];
sum[i] += sum[i - 1];
}
int ans = 0, r = 2;
for (int l = 2; l <= n + 1; l++) {
while (r < n && mn(l, r) < mn(l, r + 1)) r++;
//循环到最大的位置（这是单峰函数，才能这样写的）
ans = max(ans, mn(l, r));
//从多组起点的情况选出最大值
}
cout << ans << endl;
return 0;
}
//函数区
D-二分
AC代码
E-交换
这道题看题目要看清楚，一开始我还以为是求逆序对，但是现在才发现交换不一定相邻。
首先我们来看题目：
- 题目是说，我们要把这个数组换成有序，最少要交换多少次数据。
算法思想：
- 既然我们要知道从当前的乱序到最终的有序要进行多少步，我们可以把初态和终态保存下来做对比。
- 我们这里当然可以用两个数组来表示，但是我们还有一个简单的方法就是用结构体或者pair（就是包装过的只有两项的结构体）。
- 我这里用了pair，pair在sort时会默认按first项排升序，然后我们排序后的first项就是有序的（现在的位置），second就是以前的（乱序时的位置）。
- 那么我们就可以发现：我们的first是从second来的！与此同时，排序后second的位置也是从某一个位置来的，一直往复下去，一定会有一个节点是从first中来的（形成环）。
- 栗子：就拿3,2,1来说，最后1和3是换了位置的对吧，也就是说1和3形成了一个环。这个环移动一次就可以让数据归位。
- 从上面我们也能观察到，如果是更大的环，有n个节点的环，移动n - 1个数就能使序列有序。反过来看，就是有一个环，可以让交换次数比节点个数少1。
- 所以不难得出，我们最多数组也就是换个n次。然后有一个环就次数-1，答案不就是（n - 环数）吗（注意：<stron>呗）。 </stron>
说到判环和搜索，我们自然的就会想到dfs：
- 所以我们为了判环，加一个标记数组visited。用来表示这些节点有没有找过。
- 判环基本操作：我们以每一个节点为原点进行找环，没有被查找过就继续找，然后把这个节点所在的环遍历掉，最后计个数就好了。
dfs操作：
- 其实很简单，用个变量记录下起点，然后不停的找起点所对应的来源点。一直找到找回自己为止（这样就遍历完了一个环）。
打代码呗：
- 首先我们输入变量，存进pair嘛。
- 然后给结构体数组排个序。
- 最后判环统计就好了。
- 看我代码呗~
AC代码
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 1e5 + 7;
pair<int, int> info[MAX];
bool visited[MAX];
//全局变量区
int main() {
IOS;
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> info[i].first;
info[i].second = i;
}
sort(info + 1, info + 1 + n);
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (visited[i]) continue;
//在以前形成过环
auto it = info[i];
while (!visited[it.second]) {
visited[it.second] = true;
it = info[it.second];
}
//标记环
cnt++;//环数+1
}
cout << n - cnt << endl;
return 0;
}
//函数区
京公网安备 11010502036488号