2020-05-14

模拟栈

#include <iostream>
 using namespace std;

const int N = 100010;
int stk[N], tt;

 int main()
 {
     int n; 
     cin>>n;
     while(n--)
     {
         string op;
         int a;
         cin>>op;
         if(op == "push")
         {
             cin>>a;
             stk[++ tt] = a;
         }
         else if(op == "pop")
         {
             tt --;
         }
         else if(op == "query")
         {
             cout<<stk[tt]<<endl;
         }

         else
         {
             if(tt == 0) puts("YES");
             else puts("NO");
         }
     }
 }

模拟队列

#include <iostream>
// #include <cstring>
 using namespace std;
 
const int N = 1000010;
int q[N], hh, tt = -1; 

 int main()
 {
     int n;
     cin>>n;
     while(n--)
     {
         string op;
         cin>>op;
         if(op == "push")
         {
             int a;
             cin>>a;
             q[++ tt] = a; 
         }
         
         else if(op == "empty")
         {
             if(tt < hh) puts("YES");
             else puts("NO");
         }
         
         else if(op == "query")
         {
             cout<<q[hh]<<endl;
         }
         
         else
         {
             hh ++;
         }
     }
 }

冒泡排序

void bubble_sort()  //冒泡排序
{
    // for(int i = n - 1; i >= 0; i--) //把最大的往下沉
    // {    
    //     bool flag = false;
    //     for(int j = 0; j < i; j++)
    //         if(a[j] > a[j+1])
    //         {    swap(a[j], a[j+1]); 
    //             flag = true; } 
    //     if(!flag) break; //优化
    // }
    for(int i = 0; i < n; i++)
    {
        bool flag = false;
        for(int j = n-1; j >= i; j--)   //最小的从底网上冒
            if(a[j-1] > a[j])
            {    swap(a[j-1], a[j]);
                flag = true;}
        if(!flag) break;
    }
}

选择排序

void select_sort()  //选择排序
{
    for(int i = 0; i < n; i++)  
    {
        int k = i;
        for(int j = i+1; j < n; j++)  
            if(a[k] > a[j])
                k = j;          //把小的选上

         if(i != k)  //找到了最小值
            swap(a[i], a[k]);   //每轮交换一次
    }
}

插入排序

void insert_sort()//直接插入排序，把数插入一个已经排好序的序列
{
    for(int i = 1; i < n; i++)
    {   
        int t = a[i], j;   //先存下来
        for(j = i-1; j >= 0; j--)
            if(a[j] > t)
                a[j+1] = a[j];
            else break;
        a[j+1] = t;
    }
    // for(int i = 1; i < n; i++)
    // {
    //     int t = a[i], j;
    //     for(j = i-1; a[j] > t; j--)
    //         a[j+1] = a[j];  //比t大的往后放，排好序
    //     a[j+1] = t;         //把t放到 大于t的已排序的前面
    // }
}

快排

void quick_sort(int a[], int l, int r)
{
    if(l >= r) return;
    int i = l, j = r, mid = a[(l+r) >> 1];

    while(i < j)
    {
        while(a[i] < mid) i++;
        while(a[j] > mid) j--;
        if(i < j) swap(a[i], a[j]);
        // else break;
    }
    quick_sort(a, l, j); quick_sort(a, j+1, r);
}

归并

void merge_sort(int a[], int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(a, l, mid); 
    merge_sort(a, mid+1, r);

    static vector<int> tmp(r);//静态数组，调用快点
    tmp.clear(); //存放临时最小的，然后清空，tmp也可作为全局变量放外面

    int k = 0, i = l, j = mid+1;
    while(i <= mid && j <= r)
        if(a[i] > a[j]) 
        {
            tmp[k++] =  a[j++]; 
            res += mid-i +1; //逆序对个数
        }
        else tmp[k++] = a[i++];

    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

    for(int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}

堆排序

#include <iostream>
 using namespace std;
 const int N = 100010;
 int h[N], cnt;

 void down(int u)
 {
     int minn = u;
     if(u*2 <= cnt && h[u*2] < h[minn]) minn = u*2;
     if(u*2 + 1 <= cnt && h[u*2 + 1] < h[minn]) minn = u*2 + 1;
     if(minn != u)
     {
         swap(h[minn], h[u]);
         down(minn);
     }
 }
 int main()
 {
     int n,m;
     cin>>n>>m;
     for(int i=1; i <= n; i++) scanf("%d", &h[i]);
     cnt = n;
     for(int i = n/2; i >= 1; i--) down(i);
     while(m--)
     {
         cout<<h[1]<<" ";
         h[1] = h[cnt];
         cnt -= 1 ;
         down(1);
     }

 }

二分求数的三次方（牛顿迭代法）

#include <iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = -100, r = 100;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }

    printf("%.6lf\n", l);
    return 0;
}