算法模板
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根据题目中要求的精度来定)
标签:...,int,while,算法,m1,m2,check,模板
From: https://www.cnblogs.com/cookiebread/p/alg_muban.html