# 其实是伪代码
# 复杂度为O(n)
minV = R[0]
maxV = -20000000 #初始得设小点 虽然我觉得可以跳过第一次循环的比较来解决
for j from 1 to n-1
	maxV = max(maxV,R[j] - maxV)
    minV = min(minV,R[j])

#升序排列的插入排序
insSort(A, N)
	for i from 0 to N - 1 # 我们对每一个未排序的元素展开相关操作
    	v = A[i] #当前的“未排序”元素
        j = i - 1 #上一个元素
        while j >=0 and a[j] > v #当 当前元素上一个元素存在，且上一个元素仍然大于当前元素时
        	A[j + 1] = A[j] #我们将上一个元素“后移”一位
            j-- #移动到上上个元素
        A[j + 1] = v #如果发现之前没有元素，或者它并不大于“未排序”元素 则把未排序元素怼到这个位置上

#include <stdio.h>
void trace(int a[], int sum)
{
    for (int i = 0; i < sum; printf("%d ",a[i]), i++);
    puts("");
}
void insSort(int a[], int sum)
{
    for (int i = 0; i < sum;i++)
    {
        int v = a[i];
        int j = 0;
        for (j = i - 1; j >= 0 && a[j] >= v;a[j+1] = a[j], j--);
        a[j + 1] = v;
    }
}
int main()
{
    int testArray[] = {2, 8, 6, 8, 4, 13, 89, 20, -30};
    trace(testArray, sizeof(testArray) / sizeof(int));
    insSort(testArray, sizeof(testArray) / sizeof(int));
    puts("sorted:");
    trace(testArray, sizeof(testArray) / sizeof(int));
    return 0;
}

#升序排列
bubSort(A, N)
	flag = true #旗帜为真
    while flag #旗帜不倒
    	flag = false
        for j from N -1 to 1 #倒序遍历整个数组
        	if A[j] < A[j - 1] #若当前数比前一个小
            	swap(A[j], A[j - 1]) #换到后面去
                flag = true #旗帜为真

for j from N -1 to 1

#升序排列
bubSort(A, N)
	flag = true #旗帜为真
    i = 0 #定义未排序部分下标
    while flag #旗帜不倒
    	flag = false
        for j from N -1 to i + 1 #倒序遍历整个数组
        	if A[j] < A[j - 1] #若当前数比前一个小
            	swap(A[j], A[j - 1]) #换到后面去
                flag = true #旗帜为真
        i++

#include <stdio.h>
void trace(int a[], int sum)
{
    for (int i = 0; i < sum; printf("%d ",a[i]), i++);
    puts("");
}
void bubSort(int a[], int sum)
{
    for (int flag = 1, i = 0; flag; i++)
    {
        flag = 0;
        for (int j = sum - 1; j > i; j--)
            if(a[j] < a[j-1])
            {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
                flag = 1;
            }
    }
}
int main()
{
    int testArray[] = {2, 8, 6, 8, 4, 13, 89, 20, -30};
    trace(testArray, sizeof(testArray) / sizeof(int));
    bubSort(testArray, sizeof(testArray) / sizeof(int));
    puts("sorted:");
    trace(testArray, sizeof(testArray) / sizeof(int));
    return 0;
}

selSort(A, N)
	for i from 0 to N - 1 #遍历整个数组
    	minJ = i #初始化当前区间内最小值
        for j from i to N - 1 #遍历未排序区间
        	if A[j] < A[minJ] #确定该区间最小值下标
            	minJ = j
        swap(A[i], A[minJ]) #把最小值dia过去

#include <stdio.h>
void trace(int a[], int sum)
{
    for (int i = 0; i < sum; printf("%d ",a[i]), i++);
    puts("");
}
void selSort(int a[], int sum)
{
    for (int i = 0; i < sum; i++)
    {
        int minJ = i;
        for (int j = i; j < sum; j++)
            if(a[minJ]>a[j])
                minJ = j;
        int temp = a[i];
        a[i] = a[minJ];
        a[minJ] = temp;
    }
}
int main()
{
    int testArray[] = {2, 8, 6, 8, 4, 13, 89, 20, -30};
    trace(testArray, sizeof(testArray) / sizeof(int));
    selSort(testArray, sizeof(testArray) / sizeof(int));
    puts("sorted:");
    trace(testArray, sizeof(testArray) / sizeof(int));
    return 0;
}

init()
	top = 0
isEmpty()
	return top == 0
isFull()
	return top >= MAX - 1
push(x)
    assert(isFull())
    top++
    S[top] = x
pop()
	assert(isEmpty())
    top--
    return S[top+1]

//array stack header
#ifndef A_STACK
#define A_STACK
#define aMAX 1000
#define aCap aMAX - 1
int aTop, aS[aMAX];
void a_init()
{
    aTop = 0;
}
int a_is_empty()
{
    return aTop == 0;
}
int a_is_full()
{
    return aTop >= aCap;
}
void a_push(int x)
{
    if(a_is_full())
        return;
    aTop++;
    aS[aTop] = x;
}
int a_pop()
{
    if(a_is_empty())
        return 0;
    aTop--;
    return aS[aTop + 1];
}
#endif

#include <stdio.h>
#include <stdlib.h>
#include "array_stack.h"
int main()
{
    a_init();//初始化栈
    int a = 0, b = 0;//初始化a，b变量，用以保存两个操作数
    char buf[100];//输入缓存
    int flag = 1;//循环控制变量
    while(flag && scanf("%s", buf) != EOF)
    {
        //当读取到运算符时，取出栈中前两个元素进行运算，并将结果压回栈中
        switch (buf[0])
        {
        case '+':
            a = a_pop();
            b = a_pop();
            a_push(a + b);
            break;
        case '-':
            a = a_pop();
            b = a_pop();
            a_push(b - a);
            break;
        case '*':
            a = a_pop();
            b = a_pop();
            a_push(a * b);
            break;
        case '/':
            a = a_pop();
            b = a_pop();
            a_push(b / a);
            break;
        //循环控制终止
        case ',':
            flag = 0;
            break;
        //如果读到的不是运算符，则必然是操作数，压入栈中
        default:
            a_push(atoi(buf));
            break;
        }
    }
    //得到栈顶最终结果
    printf("calc: %d", a_pop());
    return 0;
}

init()
	head = tail = 0 #初始化 头尾指针位置 为0（一维数组起始）
isEmpty()
	return head == tail #我们认为头尾相等就是空
isFull()
	head == (tail + 1) % MAX #我们认为头尾差一格就是满 用这个表达式巧妙地体现了这个关系
enqueue(x)
	assert(isFull()) #检查非法操作
    Q[tail] = x
    tail = (tail + 1 == MAX) ? 0 : tail + 1 #将越界情况下的结果约束在数组范围
dequeue()
	assert(isEmpty()) #检查非法操作
    x = Q[head]
    head = (head + 1 == MAX) ? 0 : head + 1 #将越界情况下的结果约束在数组范围
    return x   

//circular queue header
//为了通用性，将存储类型改为void*
#ifndef C_QUEUE
#define C_QUEUE
#define cMAX 100
int cHead, cTail;
void* cQ[cMAX];
void c_init()
{
    cHead = cTail = 0;
}
int c_is_empty()
{
    return cHead == cTail;
}
int c_is_full()
{
    return cHead == (cTail + 1) % cMAX;
}
void c_enqueue(void* x)
{
    if(c_is_full())
        return;
    cQ[cTail] = x;
    cTail = (cTail + 1) % cMAX;
}
void* c_dequeue()
{
    if(c_is_empty())
        return NULL;
    void* x = cQ[cHead];
    cHead = (cHead + 1) % cMAX;
    return x;
}
#endif 

#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include "circular_queue.h"
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
int elaps = 0, count = 0, maxTime = 50, delta = 0;//时长，任务数，时间片长度，时间差值
//任务结构体定义
typedef struct myProcess
{
    char name[50];
    int timeLapse;
}P;
//跑任务的函数
void run_process()
{
    P *p = (P*)c_dequeue();//取出队列内容
    if(p != NULL)//有效值
    {
        delta = MIN(maxTime, p->timeLapse);//计算差值:考虑当前时间片是否满足剩余时长
        Sleep(p->timeLapse); //模拟玩的，可以不写
        p->timeLapse -= delta;//减去任务时间
        elaps += delta;//累加总时长
        printf("%s has run %d ms, with %d ms left.\n", p->name, delta, p->timeLapse);//输出信息
        if(p->timeLapse)//如果还有时长，重新加入队列等待执行
            c_enqueue(p);
        else
        {
            printf("%s has ended. it's %d ms now.\n", p->name, elaps);//结束信息
            free(p);//释放内存
        }
    }
    
}
int main()
{
    c_init();//初始化队列
    puts("please set task arguments.");
    scanf("%d %d", &count, &maxTime);//读入几个参数
    for (int i = 0; i < count; i++)
    {
        P *t = (P*)malloc(sizeof(P));//开辟内存，创建进程/任务
        scanf("%s %d", t->name, &t->timeLapse);//读入任务信息
        c_enqueue((void *)t);//添加进入队列
    }
    //利用一行for完成提示信息输出+调度循环
    for (puts("starting the simulation.");(!c_is_empty());run_process());
    return 0;
}

typedef struct dNode{
    int key;
    dNode *prev;
    dNode *next;
}dNode;

dNode* d_list_init()//初始化：生成一个头结点
{
    dNode *nil = (dNode *)malloc(sizeof(dNode));
    //头结点前后指针初始化均指向自身
    nil->prev = nil;
    nil->next = nil;
    return nil;
}

void d_list_ins(dNode *head, int key)//在头结点后插入一个结点
{
    if (head == NULL)
        return;
    dNode *n = (dNode *)malloc(sizeof(dNode));
    n->key = key;
    n->next = head->next;
    head->next->prev = n;
    head->next = n;
    n->prev = head;
}

dNode* d_list_search(dNode *head, int key)
{
    if (head == NULL)
        return head;
    dNode *cur;
    //从头结点的下一节点开始直到末尾遍历
    //cur != head：当刚好回到头结点（链表为空；或走完链表，因为尾结点的next就是头结点）时结束
    for (cur = head->next; cur != head && cur->key != key; cur = cur->next);
    return cur;
}

void d_list_delete(dNode *head, dNode *n)
{
    if (n == NULL || n == head)
        return;
    n->prev->next = n->next;
    n->next->prev = n->prev;
    free(n);
}

#define DLIST_DEL_FIRST(head) d_list_delete(head, head->next)
#define DLIST_DEL_LAST(head) d_list_delete(head, head->prev)
#define DLIST_DEL_AT(head, key) d_list_delete(head, d_list_search(head, key))

//double linked list header
#ifndef D_LIST
#define D_LIST
#include <malloc.h>
typedef struct dNode{
    int key;
    struct dNode *prev;
    struct dNode *next;
}dNode;
dNode* d_list_init()
{
    dNode *nil = (dNode *)malloc(sizeof(dNode));
    nil->prev = nil;
    nil->next = nil;
    return nil;
}
void d_list_ins(dNode *head, int key)
{
    if (head == NULL)
        return;
    dNode *n = (dNode *)malloc(sizeof(dNode));
    n->key = key;
    n->next = head->next;
    head->next->prev = n;
    head->next = n;
    n->prev = head;
}
dNode* d_list_search(dNode *head, int key)
{
    if (head == NULL)
        return head;
    dNode *cur;
    for (cur = head->next; cur != head && cur->key != key; cur = cur->next);
    return cur;
}
void d_list_delete(dNode *head, dNode *n)
{
    if (n == NULL || n == head)
        return;
    n->prev->next = n->next;
    n->next->prev = n->prev;
    free(n);
}
#define DLIST_DEL_FIRST(head) d_list_delete(head, head->next)
#define DLIST_DEL_LAST(head) d_list_delete(head, head->prev)
#define DLIST_DEL_AT(head, key) d_list_delete(head, d_list_search(head, key))
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "d_list.h"
int main()
{
    dNode *head = d_list_init();
    char input[100];
    int flag = 0;
    //初始化提示语句，获取正确输入，若输入为end就终止循环
    for (puts("pls enter your instructions:"); scanf("%s", input) && strcmp(input,"end");)
    {
        //判断命令类型
        if(!strcmp(input, "ins"))
            flag = 1;
        else if(!strcmp(input, "del"))
            flag = 2;
        else if(!strcmp(input, "srch"))
            flag = 3;
        else{
            flag = 0;
            puts("wrong input.");
            continue;
        }
        //获取第二个命令
        scanf("%s", input);
        //分类讨论
        switch (flag)
        {
            case 1:
                d_list_ins(head, atoi(input));
                break;
            case 2:
                switch (input[0])
                {
                case 'F':
                    DLIST_DEL_FIRST(head);
                    break;
                case 'L':
                    DLIST_DEL_LAST(head);
                    break;
                default:
                    DLIST_DEL_AT(head, atoi(input));
                    break;
                }
                puts("deleted.");
                break;
            case 3:
                if (d_list_search(head, atoi(input)) != head)
                    puts("founded.");
                else
                    puts("not founded.");
                break;
        }
    }
    //打印全部内容
    for (dNode *cur = head->next; cur != head; printf("key remains: %d\n",cur->key), cur=cur->next);
    return 0;
}

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
//定义一个存放水域的结构体
struct w_area
{
    int start_pos;//左起始点‘\’位置
    int area;//水域面积
};
int main()
{
    std::stack<int> inputs;//存放输入‘\’
    std::stack<w_area> areas;//存放所有水域
    int total = 0, i = 0;//总面积，计数（当前位置）变量
    for (char ch = '_', flag = 0; scanf("%c", &ch) && ch!='\n'; i++)//读入输入，并计数
    {
        switch (ch)
        {
            case '\\':
                inputs.push(i);//向栈中压入一个‘\’
                break;
            case '/':{
                if (!inputs.empty())//如果输入栈不为空：即当前右侧的‘/’
                {
                    int j = inputs.top();//获取最近一个‘\’的位置，其必然与当前‘/’配对
                    inputs.pop();//弹出栈
                    int a = i - j;//前后距离即为当前一组水域的面积
                    total += a;//加入总面积
                    w_area latest = {j, a};//记录当前的水域
                    //如果之前已经记录了水域
                    //且之前那组水域的起始位置更大，意味着它在新水域——即事实上更前面的一组水域之后（之下）
                    //我们更新当前水域，它将合并上一组水域（它之后水域）的面积
                    //同时弹出已经被合并掉的旧水域
                    //一直循环至无法合并为止
                    for (; (!areas.empty()) && (areas.top().start_pos > j);
                     latest.area+=areas.top().area, areas.pop());
                    //将当前水域压入栈中
                    areas.push(latest);
                }
                break;
            }
            case '_':
                break;
            default:
                puts("wrong input.");
                break;
        }
    }
    //注意：_Get_container()方法在一些环境下可能不受支持，此时考虑其他方法逆序输出即可
    auto area_content = areas._Get_container();
    printf("%d\n%d", total, area_content.size());
    for (auto it = area_content.begin(); it != area_content.end(); printf(" %d", it->area), it++);
    return 0;
}