acwing学习记录（第一节课）
（一）快排
#include<stdio.h>
#define MAX 100010
void qsort(int *a,int l,int r){
if(l>=r) return;
int mid = a[(l+r)/2];
//mid是数组中间的那个数，与归并的mid规定不同，注意区分；
//同时这样做可以不用再把标兵数放回，即不用a[i] = mid这一步。
int i = l-1;
//扩
int j = r+1;
//扩
while(i<j){
do i++;while(a[i]<mid);
do j--;while(a[j]>mid);
if(i<j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
qsort(a,l,j); //注意是a,l,j
qsort(a,j+1,r);
}
int main(){
int n;
int a[MAX];
scanf("%d",&n);
for(int i = 0;i < n ;i++){
scanf("%d",&a[i]);
}
qsort(a,0,n-1);
for(int i = 0;i < n ;i++){
printf("%d ",a[i]);
}
return 0;
}
(二)归并排序
#include<stdio.h>
#define MAX 1000010
int change[MAX];
void merge(int *a,int l,int r){
if(l>=r) return; //越界就终止
int mid = (l + r)/2; //取中间的值
merge(a,l,mid); //划为两段递归
merge(a,mid+1,r);
int i = l; //第一段的第一个数
int j = mid + 1; //第二段的第一个数
int k = 0; //临时存放数组的下标
while(i<=mid && j <=r){
//只要一个数组没递归结束，就一直选两个数组中较小的放入临时存放数组
if(a[i]<=a[j]) change[k++] = a[i++];
else change[k++] = a[j++];
}
while(i <= mid) change[k++] = a[i++];
//如果第一个数组没放完，直接全部插入即可
while(j <= r) change[k++] = a[j++];
//如果第二个数组没放完，直接全部插入即可
for(int i=l,j=0;i<=r;i++,j++)
a[i] = change[j];
}
int main(){
int n;
int a[MAX];
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
merge(a,0,n-1);
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}
归并数组的应用
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i个和第 j个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000
数列中的元素的取值范围
[1,10^9]
#include <stdio.h>
#define MAX 100010
typedef long long LL;
LL res = 0;
int change[MAX];
void merge_sort(int *a,int l,int r){
if(l>=r) return;
int mid = (l + r) / 2;
int k = 0;
merge_sort(a,l,mid); //先把两边有序分一下
merge_sort(a,mid+1,r);
int i = l;
int j = mid + 1;
while(i<=mid && j<=r){
if(a[i]<=a[j]) change[k++] = a[i++];
else{
change[k++] = a[j++];
res += mid - i + 1;
//此时左右两边都有序，所以只要发生这种情况，就是左边的数组的这个元素及其右边的元素都小于右边的这个数。
//因为排序好了，所以右边的数组的这个数的左边的数都小于右边的这个数，所以就是mid-i+1。
}
}
while(i<=mid) change[k++] = a[i++];
while(j<=r) change[k++] = a[j++];
for(int i = l,j=0;i<=r;i++,j++)
a[i] = change[j];
}
int main(){
int n;
int a[MAX];
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
}
merge_sort(a,0,n-1);
printf("%lld",res);
return 0;
}
(三)二分查找
整数二分的本质是边界。
整数二分算法（记住左“1”）
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
例题
给定一个按照升序排列的长度为 n的整数数组，以及 q个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤≤100000
1≤q≤10000
1≤k≤10000
#include <stdio.h>
#define MAXN 100010
int n;
int q;
int k;
int a[MAXN];
int main(){
scanf("%d %d",&n,&q);
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);
while(q--){
int l = 0;
int r = n - 1;
scanf("%d",&k);
while(l<r){
int mid = (l + r) / 2;
if(a[mid]>=k) r = mid;
else l = mid + 1;
}
if(a[l]!=k)
printf("-1 -1\n");
else{
printf("%d ",l);
int l = 0;
int r = n - 1;
while(l<r){
int mid = (l + r + 1) / 2;
if(a[mid]<=k) l = mid;
else r = mid - 1;
}
printf("%d\n",l);
}
}
return 0;
}
浮点数二分模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
例题
给定一个浮点数 n，求它的三次方根。
输入格式
共一行，包含一个浮点数 n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6位小数。
数据范围
−10000≤n≤10000
#include <stdio.h>
int main(){
double n;
scanf("%lf",&n);
double l = -10000;
double r = 10000;
while(r - l > 1e-8){
double mid = (l + r) / 2;
if(mid * mid * mid > n) r = mid;
else l = mid;
}
printf("%lf\n",l);
return 0;
}
投递美团等公司10个岗位 >