算法模板

1.排序

(1)快速排序(No STL)

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100010];

void dfs(int l,int r)
{
	if(l >= r)
		return ;
	int pos = (l + r) >> 1;
	int x = a[pos];
	int i = l,j = r;
	while(i <= j)
	{
		while(a[i] < x)
			i++;
		while(a[j] > x)
			j--;
		if(i <= j)
			swap(a[i],a[j]),i++,j--;
	}
	dfs(l,j);
	dfs(i,r);
}

signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	dfs(1,n);
	for(int i = 1; i <= n; i++)
		cout << a[i] << " ";
	cout << "\n";
	return 0;
}

2.二分

(1)整数三分

int l = ...,r = ...,ans = ...;
while(r - l >= 3)
{
	int m1 = l + (r - l) / 3;
	int m2 = r - (r - l) / 3;
	if(f(m1) > f(m2))
		ans = l,l = m1 + 1;
	else
		r = m2 - 1;
}
while(l <= r)
{
	if(f(l) < f(ans))
		ans = l;
	l++;
}

(2)小数三分

double l = ...,r = ...;
while(l + eps < r)
{
	double m1 = (l + l + r) / 3.0;
	double m2 = (l + r + r) / 3.0;
	if(check(m1) < check(m2))
		r = m2;
	else
		l = m1;
}

然后答案是check(l)或者l

(其中的eps根据题目中要求的精度来定)