E:快速排序
题目描述
本题为代码补全填空题，请将题目中给出的源代码补全，并复制到右侧代码框中，选择对应的编译语言（C/Java）后进行提交。若题目中给出的源代码语言不唯一，则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉，填上你的答案。提交后若未能通过，除考虑填空部分出错外，还需注意是否因在复制后有改动非填空部分产生错误。
以下代码可以从数组 a[ ] 中找出第 k小的元素。
它使用了类似快速排序中的分治算法，期望时间复杂度是O(N)的。
请仔细阅读分析源码，填写划线部分缺失的内容。
源代码
C
#include <stdio.h> int quick_select(int a[], int l, int r, int k) { int p = rand() % (r - l + 1) + l; int x = a[p]; {int t = a[p]; a[p] = a[r]; a[r] = t;} int i = l, j = r; while(i < j) { while(i < j && a[i] < x) i++; if(i < j) { a[j] = a[i]; j--; } while(i < j && a[j] > x) j--; if(i < j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quick_select( _____________________________ ); //填空 else return quick_select(a, l, i - 1, k); } int main() { int a[100]; int n; scanf("%d %d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); printf("%d\n", quick_select(a, 0, n-1, 5)); return 0; }
java
import java.util.Scanner; import java.util.Random; public class Main{ public static int quickSelect(int a[], int l, int r, int k) { Random rand = new Random(); int p = rand.nextInt(r - l + 1) + l; int x = a[p]; int tmp = a[p]; a[p] = a[r]; a[r] = tmp; int i = l, j = r; while(i < j) { while(i < j && a[i] < x) i++; if(i < j) { a[j] = a[i]; j--; } while(i < j && a[j] > x) j--; if(i < j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quickSelect( _________________________________ ); //填空 else return quickSelect(a, l, i - 1, k); } public static void main(String args[]) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int a[]=new int[110]; for(int i=0;i<n;i++) { a[i]=scan.nextInt(); } System.out.println(quickSelect(a, 0, n-1, 5)); } }
运行限制
最大运行时间：1s
最大运行内存: 256M
我是用的c，首先添加头文件#include <stdlib.h>，随机函数rand()用。
首先快速排序要找一个基点，题目中是随机的，然后放到最后一位。左指针向右移动直到找到一个大于基数的数，将其复制到最后，随后右指针向左移动，直到找到一个小于基数的数，将其赋予左指针，以此循环，最后左右指针碰头，将基点赋予该位置。这样导致基点右边都是大于基点，左边都是小于基点。然后判断基点下标（以未移动的左指针开始算）适合符合。
#include <stdio.h> #include <stdlib.h> int quick_select(int a[], int l, int r, int k) { int p = rand() % (r - l + 1) + l; int x = a[p]; {int t = a[p]; a[p] = a[r]; a[r] = t;} int i = l, j = r; while(i < j) { while(i < j && a[i] < x) i++; if(i < j) { a[j] = a[i]; j--; } while(i < j && a[j] > x) j--; if(i < j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quick_select(a,i+1,r,k-i+l-1); //因为已经有i-l+1个小于的数了。 else return quick_select(a, l, i - 1, k); } int main() { int a[100]; int n; scanf("%d %d",&n); for(int i=0;i<n;i++) //输入n个数 scanf("%d",&a[i]); printf("%d\n", quick_select(a, 0, n-1, 5)); return 0; }
F:递增三元组
题目描述
给定三个整数数组
A = A1,A2,⋯AN],
B=[B1,B2,⋯BN],
C=[C1,C2,⋯CN]，
请你统计有多少个三元组 (i,j,k) 满足：
N1≤i,j,k≤N;
Ai<Bj<Ck。
输入描述
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋯AN。
第三行包含 N 个整数 B1,B2,⋯BN。
第四行包含 N 个整数 C1,C2,⋯CN。
其中1≤N≤105,0≤Ai,Bi,Ci≤105。
输出描述
输出一个整数表示答案。
输入输出样例
示例
输入
3 1 1 1 2 2 2 3 3 3
输出
27
运行限制
最大运行时间：2s
最大运行内存: 256M
#include <iostream> #include <algorithm> using namespace std; int n; int a[100005]; int b[100005]; int c[100005]; long long ans; int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=0;i<n;i++){ cin>>b[i]; } for(int i=0;i<n;i++){ cin>>c[i]; } sort(a,a+n); sort(b,b+n); sort(c,c+n); int m=0; int mm=0; int j = 0; int k = 0; //以b为中间值 在a数组 c数组中查找 for(int i=0;i<n;i++){ while(j<n && a[j] < b[i]) j++; while(k<n && c[k] <= b[i]) k++; ans += (long long)(j) * (n-k); } cout<<ans<<endl; return 0; }
G:螺旋折线
题目描述
如下图所示的螺旋折线经过平面上所有整点恰好一次。
对于整点 (X,Y)，我们定义它到原点的距离dis(X,Y) 是从原点到 (X,Y)的螺旋折线段的长度。
例如 dis(−2,−1)=9。
给出整点坐标 (X,Y)，你能计算出 dis(X,Y) 吗？
输入描述
输入格式：
输入一行，X 和 Y ，−109≤X,Y≤109。
输出描述
输出 dis(X,Y)。
输入输出样例
示例
输入
0 1
输出
3
运行限制
最大运行时间：1s
最大运行内存: 256M
曼哈顿距离方法比较简单，一开始我是每个象限推导，好麻烦的。然后看到网上有曼哈顿距离。
#include <iostream> #include <cmath> using namespace std; long long x,y; long long ans; int main(){ cin>>x>>y; long long t=max(abs(x),abs(y)); if(x>=y){ ans=4*t*t+abs(x-t)+abs(y-t); }else{ ans=4*t*t-abs(x-t)-abs(y-t); } cout<<ans; return 0; }
