Algorithms and Data Structures I

Vintage 80s office by Mohamed Chahin

引言

Acquire fundamental elements of algorithms and data structures.

Topic #1 Getting Started

ALDS1_1_A Insertion Sort

Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

for i = 1 to A.length-1
    key = A[i]
    /* insert A[i] into the sorted sequence A[0,...,j-1] */
    j = i - 1
    while j >= 0 and A[j] > key
        A[j+1] = A[j]
        j--
    A[j+1] = key

Note that, indices for array elements are based on 0-origin.

To illustrate the algorithms, your program should trace intermediate result for each step.

Input

The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by a single space.

Output

The output consists of N lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space.

Constraints

1 ≤ N ≤ 100

Sample Input 1

6
5 2 4 6 1 3

Sample Output 1

5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3
1 2 3
1 2 3

問題を解く

算法原理

本题要求我们实现插入排序算法并输出升序排列过程。在插入排序的过程中，会将整体数组分成“已排序部分”和“未排序部分”，题目中已经给出了插入排序的伪代码，我们可以先翻译一下整个排序过程：

将开头元素视为已排序
执行下述处理，直至未排序部分消失：
	1. 取出未排序部分的开头元素赋给变量v
	2. 在已排序的部分，将所有比v大的元素向后移一个单位
	3. 将已取出的元素v插入空格

如果这段话不是很好理解，我们可以用下图来阐释排序的整个过程：

再举个例子，我们对数组A={8,3,1,5,2,1}进行插入排序时，整体流程如下：

0: 8 3 1 5 2 1
1: 3 8 1 5 2 1
2: 1 3 8 5 2 1
3: 1 3 5 8 2 1
4: 1 2 3 5 8 1
5: 1 1 2 3 5 8

在步骤1中，将开头元素A[0]（=8）视为已排序，所以我们去除A[1]的3，将其插入已排序部分的恰当位置。首先把原先位于A[0]的8移动至A[1]，再把3插入A[0]。这样一来，开头2个元素就完成了排序。

在步骤2中，我们要把A[2]的1插入恰当位置。这里首先将比1大的A[1]（=8）和A[0]（=3）顺次向后移一个位置，然后把1插入A[0]。

在步骤3中，我们要把A[3]的5插入恰当位置。这次将比5大的A[2]（=8）向后移一个位置，然后把5插入A[2]。

之后同理，将已排序部分的其中一段向后移动，再把未排序部分的开头元素插入已排序部分的恰当位置。插入排序的特点在于，只要0到第i号元素全部排入已排序部分，那么无论后面如何插入，这个0到第i号的元素将永远保持排序完毕的状态。

代码实现

回到代码实现，首先我们先将主函数的输入部分和单独的输出部分trace()函数写出来：

#include <iostream>
using namespace std;

void trace(int arr[],int n){
    for (int i = 0; i < n; ++i) {
        if (i == 0)
            cout << arr[i];
        else
            cout << " " << arr[i];
    }
    cout << endl;
}

int main(){
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    return 0;
}

准备工作完成后开始写insertionSort()插入排序的函数：

i：循环变量，表示未排序部分的开头元素
key：临时保存arr[i]值的变量
j：循环变量，用于在已排序部分寻找key的插入位置

void insertionSort(int arr[],int n){
    int j,key;

    for (int i = 0; i < n; ++i) {
        key = arr[i];

        j = i - 1;
        while (j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
        trace(arr,n);
    }
}

外层循环的i自增。在每次循环开始时，将arr[i]的值临时保存在变量key中。

接下来是内部循环。我们要从已排序的部分找出比key大的元素并让它们顺次后移一个位置。这里我们让j从i-1开始向前自减，同时将比key大的元素从arr[j]移动到arr[j+1]。一旦j等于-1或当前arr[j]小于等于key则结束循环，并将key插入当前j+1的位置。

#include <iostream>
using namespace std;

void trace(int arr[],int n){
    for (int i = 0; i < n; ++i) {
        if (i == 0)
            cout << arr[i];
        else
            cout << " " << arr[i];
    }
    cout << endl;
}

void insertionSort(int arr[],int n){
    int j,key;

    for (int i = 0; i < n; ++i) {
        key = arr[i];

        j = i - 1;
        while (j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
        trace(arr,n);
    }
}


int main(){
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    insertionSort(arr,n);

    return 0;
}

注意点

数组长度是否足够长
是否搞错了0起点和1起点的数组下标
是否误用了循环变量（比如i、j）
是否输出了多余的空格或换行

思考

在插入排序中，我们只将比key（取出的值）大的元素向后平移，不相邻的元素不会直接交换位置，因此整个排序算法十分稳定。

然后我们考虑一下插入排序算法的复杂度。这里需要估算每个i循环中arr[j]元素向后移动的次数。最坏情况下，每个i循环都需要执行i次移动，总共需要$1+2+…+N-1=(N^2-N)/2$次移动，即算法复杂度为$O(N^2)$。

插入排序是一种很有趣的算法，输入数据的顺序能大幅影响它的复杂度。我们前面说它的复杂度为$O(N^2)$，也仅是指输入数据为降序排列的情况。如果输入数据为升序排列，那么arr[j]从头到尾都不需要移动，程序仅需要经历N次比较便可执行完毕。可见，插入排序法的优势在于能快速处理相对有序的数据。

ALDS1_1_B Common Divisor Greatest

Write a program which finds the greatest common divisor of two natural numbers a and b

Input

a and b are given in a line sparated by a single space.

Output

Output the greatest common divisor of a and b.

Constrants

1 ≤ a, b ≤ 109

Hint

You can use the following observation:

For integers x and y, if x ≥ y, then gcd(x, y) = gcd(y, x%y)

Sample Input 1

54 20

Sample Output 1

Sample Input 2

147 105

Sample Output 2

問題を解く

最大公因数
最大公因数，也称最大公约数，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b）。求最大公约数有多种方法，常见的有质因数分解法、辗转相除法等等。

欧几里得算法
欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。欧几里得算法在RSA加密算法中有运用。

算法分析
算法通过连续计算余数，知道余数是0为止，最后所得的非0余数就是最大公因数。例如 M=1989 ，N=1590，则余数序列为399，393，6，3，0。因而，Gcd(1989,1590)=3，从余数的序列可知，这是一个快速收敛的算法。

#include <iostream>
using namespace std;

int gcd(int m, int n) {
    int r;
    while (n > 0) {
        r = m % n;
        m = n;
        n = r;
    }
    return m;
}

int main() {
    int m, n;
    cin >> m >> n;
    cout << gcd(m, n) << endl;

    return 0;
}

ALDS1_1_C Prime Numbers

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5 and 7.

Write a program which reads a list of N integers and prints the number of prime numbers in the list.

Input

The first line contains an integer N, the number of elements in the list.

N numbers are given in the following lines.

Output

Print the number of prime numbers in the given list.

Constraints

1 ≤ N ≤ 10000

2 ≤ an element of the list ≤ 108

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

問題を解く

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数，这样的数称为质数。

判断一个数 n 是否为质数，n 是否能被 [2,sqrt(n)] 间的整数整除：

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int num) {
    if (num == 2 || num == 3) return true;

    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0)
            return false;
    }
    return true;
}

int main() {
    int N, num, count = 0;
    cin >> N;

    for (int i = 0; i < N; ++i) {
        cin >> num;
        if (isPrime(num))
            count++;
    }

    cout << count << endl;
    return 0;
}

ALDS1_1_D Maximum Profit

You can obtain profits from foreign exchange margin transactions. For example, if you buy 1000 dollar at a rate of 100 yen per dollar, and sell them at a rate of 108 yen per dollar, you can obtain (108 - 100) × 1000 = 8000 yen.

Write a program which reads values of a currency $R_t$ at a certain time $t$ ($t=0,1,2,…n−1$), and reports the maximum value of $R_j−R_i$ where $j>i$ .

Input

The first line contains an integer nn. In the following nn lines, $R_t$ ($t=0,1,2,…n−1$) are given in order.

Output

Print the maximum value in a line.

Constraints

2≤n≤200,000
1≤$R_t$≤$10^9$

Sample Input 1

Sample Output 1

价格为 1 时买入、为 4 时卖出可获得 4 - 1 = 3 的最大利益。虽然取最开始的 5 有 5 - 1 = 4 > 3，但 5 的时间在 1 之前，不符合实际情况。

Sample Input 2

Sample Output 2

-1

由于我们的问题要求程序在 j > i 的条件下完成 1 次买卖操作，因此得出最大利益为 -1。

問題を解く

首先我们可以使用暴力算法遍历所有可能组合的情况：

for j from 1 to n-1
	for i from 0 to j-1
		maxv = max(maxv, R[j] - R[i]);

这个算法虽然可以获取正确的输出，但其复杂度高达 $O(n^2)$，考虑到输入上限会发现当输入较大时该程序无法在限制时间内完成处理，因此我们需要更高效的算法。

minv = R[0];
for j from 1 to n-1
	maxv = max(maxv, R[j] - minv);
	minv = min(minv, R[j]);

原先的简单算法时关于 n 的二重循环，复杂度为 $O(n^2)$。经我们改良之后，算法中仅包含一个循环，复杂度降低至 $O(n)$。另外改良后的算法不需要将输入数据保存在数组之内，因此同时也改善了内存的使用量：

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, input;
    int minv, maxv = -1000000000;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> input;
        if (i == 0) {
            minv = input;
            continue;
        }

        maxv = max(maxv, input - minv);
        minv = min(minv, input);
    }

    cout << maxv << endl;
    return 0;
}

Topic # 2 Sort I

ALDS1_2_A Bubble Sort

Write a program of the Bubble Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

BubbleSort(A)
  for i = 0 to A.length-1
     for j = A.length-1 downto i+1
         if A[j] < A[j-1]
             swap A[j] and A[j-1]

Note that, indices for array elements are based on 0-origin.

Your program should also print the number of swap operations defined in line 4 of the pseudocode.

Input

The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by spaces characters.

Output

The output consists of 2 lines.

In the first line, please print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.

In the second line, please print the number of swap operations.

Constraints

1 ≤ N ≤ 100

Sample Input 1

5
5 3 2 4 1

Sample Output 1

1 2 3 4 5
8

Sample Input 2

6
5 2 4 6 1 3

Sample Output 2

1 2 3 4 5 6
9

問題を解く

算法原理

本题要求我们实现冒泡排序算法并输出升序排列过程。与插入排序一样，冒泡排序的各个计算步骤中，数组也分成“已排序部分”和“未排序部分”。题目中已经给出了插入排序的伪代码，我们可以先翻译一下整个排序过程：

重复执行下述处理，直到数组中不包含顺序相反的相邻元素：
	从数组末尾开始依次比较相邻两个元素，如果大小关系相反则交换位置

如果这段话不是很好理解，我们可以用下图来阐释排序的整个过程：

代码实现

#include <iostream>
using namespace std;

void trace(int A[], int N) {
    for (int i = 0; i < N; ++i) {
        if (i > 0) cout << " ";

        cout << A[i];
    }
    cout << endl;
}

int bubbleSort(int A[], int N) {
    int count = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = N - 1; j >= i; --j) {
            if (A[j] < A[j - 1]) {
                swap(A[j], A[j - 1]);
                count++;
            }
        }
    }
    trace(A, N);
    return count;
}

int main() {
    int N;
    cin >> N;

    int A[N];
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    cout << bubbleSort(A, N) << endl;
    return 0;
}

思考

冒泡排序仅对数组中的相邻元素进行比较和交换，因此键相同的元素不会改变顺序。所以冒泡排序也属于一种稳定排序的算法。但要注意的是，一旦将比较运算arr[j] < arr[j - 1]改为arr[j] <= arr[j - 1]，算法就会失去稳定性。

然后我们来考虑一下冒泡排序的复杂度。假设数据总量为N，冒泡排序需对未排序部分的相邻元素进行$(N-1)+(N-2)+…+1=(N^2-N)/2$次比较。也就是说，冒泡排序在最坏的情况下需要进行$(N^2-N)/2$次比较运算，算法复杂度数量级为$O(N^2)$。

顺便一提，冒泡排序中的交换次数又称为反序数或逆序数，可用于体现数列的错乱程度。

ALDS1_2_B Selection Sort

Write a program of the Selection Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

SelectionSort(A)
  for i = 0 to A.length-1
      mini = i
      for j = i to A.length-1
          if A[j] < A[mini]
              mini = j
      swap A[i] and A[mini]

Note that, indices for array elements are based on 0-origin.

Your program should also print the number of swap operations defined in line 6 of the pseudocode in the case where i ≠ mini.

Input

The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by space characters.

Output

The output consists of 2 lines.

In the first line, please print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.

In the second line, please print the number of swap operations.

Constraints

1 ≤ N ≤ 100

Sample Input 1

6
5 6 4 2 1 3

Sample Output 1

1 2 3 4 5 6
4

Sample Input 2

6
5 2 4 6 1 3

Sample Output 2

1 2 3 4 5 6
3

問題を解く

步骤 0 为初始状态，此时所有元素均属于未排序部分。

在步骤 1 中，我们找出未排序部分最小值的位置（ minj = 6 )，然后将该位置的元素 A[6]( =1 ) 与未排序部分的起始元素 A[0]( = 5)进行交换。这样一来，已排序部分就增加了一个元素。

在步骤 2 中，找出未排序部分最小值的位置（ minj = 5 )，然后将该位置的元素 A[5]( = 3) 与未排序部分的起始元素 A[l]( = 4) 进行交换。后面的步骤同理，从数组开头按由小到大的顺序逐个确定每个位置的值。实现选择排序法时需要的主要变量如图 3.7 所示

现在，让我们回过头来看看这三种排序算法（冒泡、选择、插入），比较一下它们的特征。

冒泡排序法与选择排序法相比，一个从局部入手减少逆序元素，一个放眼大局逐个选择最小值，二者思路大不相同。但是，它们又都有着 “通过 i 次外层循环，从数据中顺次求岀 i 个最小值” 的相同特征。相对地，插入排序法是通过 i 次外层循环，直接将原数组的 i 个元素重新排序。另外，不含 flag 的简单冒泡排序法和选择排序法不依赖数据，即比较运算的次数（算法复杂度）不受输入数据影响，而插入算法在执行时却依赖数据，处理某些数据时具有很高的效率。

ALDS1_2_C Stable Sort

Let’s arrange a deck of cards. There are totally 36 cards of 4 suits(S, H, C, D) and 9 values (1, 2, … 9). For example, ‘eight of heart’ is represented by H8 and ‘one of diamonds’ is represented by D1.

Your task is to write a program which sorts a given set of cards in ascending order by their values using the Bubble Sort algorithms and the Selection Sort algorithm respectively. These algorithms should be based on the following pseudocode:

BubbleSort(C)
  for i = 0 to C.length-1
      for j = C.length-1 downto i+1
          if C[j].value < C[j-1].value
              swap C[j] and C[j-1]
SelectionSort(C)
  for i = 0 to C.length-1
      mini = i
      for j = i to C.length-1
          if C[j].value < C[mini].value
              mini = j
      swap C[i] and C[mini]

Note that, indices for array elements are based on 0-origin.

For each algorithm, report the stability of the output for the given input (instance). Here, ‘stability of the output’ means that: cards with the same value appear in the output in the same order as they do in the input (instance).

Input

The first line contains an integer N, the number of cards.

N cards are given in the following line. Each card is represented by two characters. Two consecutive cards are separated by a space character.

Output

In the first line, print the arranged cards provided by the Bubble Sort algorithm. Two consecutive cards should be separated by a space character.

In the second line, print the stability (“Stable” or “Not stable”) of this output.

In the third line, print the arranged cards provided by the Selection Sort algorithm. Two consecutive cards should be separated by a space character.

In the fourth line, print the stability (“Stable” or “Not stable”) of this output.

Constraints

1 ≤ N ≤ 36

Sample Input 1

5
H4 C9 S4 D2 C3

Sample Output 1

D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

Sample Input 2

2
S1 H1

Sample Output 2

S1 H1
Stable
S1 H1
Stable

問題を解く

由于本题中的 N 值较小，因此我们在检查排序结果是否稳定时，可以用 Program 3.2 中的这种比较笨的 $o(N^4)$ 算法：

isStable(in, out)
	for i = 0 to N - 1
		for j = i + 1 to N - 1
			for a = 0 to N - 1
				for b = a + 1 to N - 1
					if in[i].num == in[j].num
                    	return false
    return true

本题中使用 $O(N^4)$ 的算法足以满足要求，但在处理 N 更大的问题时，就需要多花些心思了。冒泡排序法属于稳定排序算法，因此输出永远都是“Stable”。然而，选择排序法是一种不稳定的排序算法，因此必须检查输出结果。其实，我们可以将选择排序的结果与冒泡排序的结果相比较，如此一来只用 $O(N)$ 便能解决问题。

#include <iostream>
using namespace std;

struct Card {
    char suit;
    int value;
};

bool operator< (Card c1, Card c2) {
    return c1.value < c2.value;
}

void trace(Card A[], int N) {
    for (int i = 0; i < N; ++i) {
        if (i > 0) cout << " ";
        cout << A[i].suit << A[i].value;
    }
    cout << endl;
}

void bubbleSort(Card A[], int N) {
    for (int i = 0; i < N; ++i) {
        for (int j = N - 1; j >= i + 1; --j) {
            if (A[j] < A[j - 1])
                swap(A[j], A[j - 1]);
        }
    }
}

void insertionSort(Card A[], int N) {
    for (int i = 0; i < N; ++i) {
        int minj = i;
        for (int j = i; j < N; ++j) {
            if (A[j] < A[minj])
                minj = j;
        }
        swap(A[i], A[minj]);
    }
}

bool isStable(Card C1[], Card C2[], int N) {
    for (int i = 0; i < N; ++i) {
        if (C1[i].suit != C2[i].suit)
            return false;
    }
    return true;
}

int main() {
    int N;
    Card C1[50], C2[50];
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> C1[i].suit >> C1[i].value;
        C2[i] = C1[i];
    }

    bubbleSort(C1, N);
    insertionSort(C2, N);

    trace(C1, N);
    cout << "Stable" << endl;
    trace(C2, N);
    if (isStable(C1, C2, N))
        cout << "Stable" << endl;
    else
        cout << "Not stable" << endl;

    return 0;
}

ALDS1_2_D Shell Sort

Shell Sort is a generalization of Insertion Sort to arrange a list of nn elements AA.

insertionSort(A, n, g)
    for i = g to n-1
        v = A[i]
        j = i - g
        while j >= 0 && A[j] > v
            A[j+g] = A[j]
            j = j - g
            cnt++
        A[j+g] = v

shellSort(A, n)
   cnt = 0
   m = ?
   G[] = {?, ?,..., ?}
   for i = 0 to m-1
       insertionSort(A, n, G[i])

A function shellSort(A, n) performs a function insertionSort(A, n, g), which considers every g-th elements. Beginning with large values of gg, it repeats the insertion sort with smaller g.

Your task is to complete the above program by filling ?. Write a program which reads an integer n and a sequence A, and prints m, $G_i(i=0,1,…,m−1)$ in the pseudo code and the sequence A in ascending order. The output of your program must meet the following requirements:

1 ≤ m ≤ 100
0 ≤ $G_i$ ≤ n
cnt does not exceed ⌈$n^{1.5}$⌉

Input

In the first line, an integer nn is given. In the following nn lines, $A_i(i=0,1,…,n−1)$ are given for each line.

Output

In the first line, print an integer mm. In the second line, print m integers $G_i(i=0,1,…,m−1)$ separated by single space character in a line.
In the third line, print cnt in a line. In the following nn lines, print $A_i(i=0,1,…,n−1)$$ respectively.

This problem has multiple solutions and the judge will be performed by a special validator.

Constraints

1 ≤ n ≤ 1,000,000
0 ≤ $A_i$ ≤ $10^9$

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

問題を解く

我们之前提到过，插入排序法可以高速处理顺序较整齐的数据，而希尔排序法就是充分发挥插人排序法这一特长的高速算法。希尔排序法中，程序会重复进行以间隔为 $g$ 的元素为对象的插入排序。举个例子，设 $g$ 的集合为 $G$，对 $A = {4,8,9,1,10,6,2,5,3, 7}$ 进行 $G ={4,3,1}$ 的希尔排序，其整体过程如图 3.9 所示。

图 3.9 中，我们按照处理顺序自上而下地列出了数组元素的变化:，每一步计算中，程序都将 $A[i]$ ( 最后一个深灰色元素）插入前方间隔为 $g$ 的元素列（此时已经排序完毕）的恰当位置。图右侧的补充说明，是为了标出各组间隔为 $g$ 的插入排序。这里请注意，程序的处理顺序与组的顺序无关。

要想完成数据排序必须在最后执行 $g = 1$，即普通的插入排序法。不过，此时对象数据的顺序应该已经很整齐了。

$g = G_i$ 的选择方法数不胜数，至今为止人们已对其进行了许多研究，不过其相关解析超出 r本书的范围，所以这里仅给各位举个例子：当 $g= 1,4,13,40,121…$，即 $g_{n + 1} = 3g_n + l$ 时，算法的复杂度基本维持在 $O(N^{1.25})$。除上述数列外，只要使用最终值为 1 的递减数列，基本都能高效地完成数据排序。不过，如果遇到 2 的幂指数（$ 2^n = 1,2,4,8…$ ）等 1 之前几乎不需要排序的数列，希尔排序法的效率会大打折扣。

#include <iostream>
#include <vector>
using namespace std;

int n;
int A[1000000];
long long cnt;
vector<int> G;

void insertSort(int A[], int n, int g) {
    for (int i = g; i < n; ++i) {
        int v = A[i];
        int j = i - g;
        while (j >= 0 && A[j] > v) {
            A[j + g] = A[j];
            j -= g;
            cnt++;
        }
        A[j + g] = v;
    }
}

void shellSort(int A[], int n) {
    for (int h = 1; ; ) {
        if (h > n) break;
        G.push_back(h);
        h = 3 * h + 1;
    }

    for (int i = G.size() - 1; i >= 0; --i) {
        insertSort(A, n, G[i]);
    }
}

int main() {
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    cnt = 0;

    shellSort(A, n);
    cout << G.size() << endl;
    for (int i = G.size() - 1; i >= 0; --i) {
        cout << G[i];
        if (i) cout << " ";
    }
    cout << endl;
    cout << cnt << endl;

    for (int i = 0; i < n; ++i) {
        cout << A[i] << endl;
    }

    return 0;
}

Topic # 3 Elementary data structures

要想实现高效的算法，离不开高效管理数据的 “数据结构”。长期以来，人们针对各种问题开发了种类繁多的数据结构。

本章就将带领各位求解一些与初等数据结构有关的问题。

ALDS1_3_A Stack

Reverse Polish notation is a notation where every operator follows all of its operands. For example, an expression (1+2)*(5+4) in the conventional Polish notation can be represented as 1 2 + 5 4 + * in the Reverse Polish notation. One of advantages of the Reverse Polish notation is that it is parenthesis-free.

Write a program which reads an expression in the Reverse Polish notation and prints the computational result.

An expression in the Reverse Polish notation is calculated using a stack. To evaluate the expression, the program should read symbols in order. If the symbol is an operand, the corresponding value should be pushed into the stack. On the other hand, if the symbols is an operator, the program should pop two elements from the stack, perform the corresponding operations, then push the result in to the stack. The program should repeat this operations.

Input

An expression is given in a line. Two consequtive symbols (operand or operator) are separated by a space character.

You can assume that +, - and * are given as the operator and an operand is a positive integer less than 106

Output

Print the computational result in a line.

Constraints

2 ≤ the number of operands in the expression ≤ 100
1 ≤ the number of operators in the expression ≤ 99
-1 × $10^9$ ≤ values in the stack ≤ $10^9$

Sample Input 1

1 2 +

Sample Output 1

Sample Input 2

1 2 + 3 4 - *

Sample Output 2

-3

Notes

Template in C

問題を解く

逆波兰表示法是一种将运算符写在操作数后面的描述程序（算式）的方法。举个例子，我们平常用中缀表示法描述的算式（ 1 + 2 ) * ( 5 + 4 )，改为逆波兰表示法之后则是 1 2 + 54 + *。相较于中缀表示法，逆波兰表示法的优势在于不需要括号。

用逆波兰表示法描述的算式可以借助栈进行运算。如图 4.2 所示，程序在计算时从算式开头逐一读取字符串，如果字符串是操作数（数值）则压入栈，如果是运算符（ + 、 - 、* ) 则从栈中取出两个数值算出结果再压入栈，如此循环。最终栈中剩下的数值便是答案。

栈等数据结构可以通过多种方法来实现，比如使用数组或表（指针）。本书重点带领各位理解数据结构的操作和限制，因此这里用数组来实现存储整型数据的栈。用数组实现栈主要需要以下变量及函数：

用来存储数据的一维整型数组：S
push 来的数据存储在数组 S 的各元素之中。需要根据问题内容保证充足的内存空间。另外，这里介绍的实现方法中 S[0] —直为空，图 4.3 所示的情况代表容量为 5 的栈中已压入了 3 个元素
用作栈顶指针的整型变量：top
指明了栈顶部（栈顶）元素（最后被添加的元素）的整型变量。top 表示最后一个被添加的元素存储在什么位置。这个变量称为栈顶指针。另外，top 的值与栈中元素的数量相等
向栈中添加元素 x 的函数：push(x)
top 增加 1，x 代入 S[top]
从栈顶取出元素的函数：pop()
返回 S[top] 的值，top 减少 1

下面我们来看看实际操作栈时的样子。图 4.4 所示的是一个由数组构成的栈，我们随意选了一些值来演示栈的压入和取出。数据结构的操作是一个动态过程，因此栈的元素也是时常变化的：

原生栈

push(x) 送来的元素在 top 加 1 之后插入 S[top]。相对地，pop() 返回 top 所指的元素，然后让 top 减一。

由数组构成的栈可以通过下述伪代码实现。

initialize()
	top = 0;
	
isEmpty()
	return top == 0;
	
isFull()
    return top >= MAX - 1;

push(x)
    if isFull()
        error()
	top++;
	s[top] = x;

pop()
    if isEmpty()
        error()
    top--;
	return S[top + 1]

initialize 函数将 top 置 0, 清空栈。此时数组（内存）中的元素虽然还在，但会被之后的 push 操作覆盖。isEmpty 函数通过检查 top 是否为 0 来判断栈中有无元素
isFull 函数用于判断栈是否已满。比方说，我们用作栈的 0 起点数组的容量为 MAX，那么 top 大于或等于 MAX - 1 时栈就是满的
push 函数会将 top 加 1，然后在 top 所指的位置添加元素 x。另外，在栈已满的状态下进行报错处理
pop 函数返冋 top 所指的元素，即位于栈顶的元素，同时将 top 减一，将栈顶元素删除。另外，在栈为空的状态下进行报错处理

设计、实现数据结构时，我们要估算对其执行各种操作时的复杂度。本题介绍了以数组为基础的栈操作，考虑到对栈顶指针的加、减以及数组的代入运算，pop 与 push 的复杂度都为 $O(1)$。

标准库

#include <iostream>
#include <stack>
#include <cstdlib>
#include <cctype>
using namespace std;

int main(){
    stack<int> st;
    string s;

    while(cin >> s){
        if(isdigit(s[0])){
            st.push(atoi(s.c_str()));
        }
        else{
            int a = st.top(); st.pop();
            int b = st.top(); st.pop();

            if(s == "+") st.push(b + a);
            if(s == "-") st.push(b - a);
            if(s == "*") st.push(b * a);
        }
    }

    cout << st.top() << endl;
}

这里的 atoi() 是 C 语言标准库中的函数，用于将自负串形式的数字转换为整型数值。

ALDS1_3_B Queue

There are n processes in a queue. Each process has namei and timei. The round-robin scheduling handles the processes in order. A round-robin scheduler gives each process a quantum (a time slot) and interrupts the process if it is not completed by then. The process is resumed and moved to the end of the queue, then the scheduler handles the next process in the queue.

For example, we have the following queue with the quantum of 100ms.

A(150) - B(80) - C(200) - D(200)

First, process A is handled for 100ms, then the process is moved to the end of the queue with the remaining time (50ms).

B(80) - C(200) - D(200) - A(50)

Next, process B is handled for 80ms. The process is completed with the time stamp of 180ms and removed from the queue.

C(200) - D(200) - A(50)

Your task is to write a program which simulates the round-robin scheduling.

Input

n q
$name_1$ $time_1$
$name_2$ $time_2$
…
$name_n$ $time_n$

In the first line the number of processes n and the quantum q are given separated by a single space.

In the following n lines, names and times for the n processes are given. namei and timei are separated by a single space.

Output

For each process, prints its name and the time the process finished in order.

Constraints

1 ≤ n ≤ 100000
1 ≤ q ≤ 1000
1 ≤ $time_i$ ≤ 50000
1 ≤ length of $name_i$ ≤ 10
1 ≤ Sum of $time_i$ ≤ 1000000

Sample Input 1

Sample Output 1

Notes

Template in C

問題を解く

现有名称为 $name_i$ 且处理时间为的 $time_i$ 个任务按顺序排成一列，CPU 通过循环调度法逐一处理这些任务，每个任务最多处理 q ms （这个时间称为时间片）。如果 q ms 之后任务尚未处理完毕，那么该任务将被移动至队伍最末尾，CPU 随即开始处理下一个任务。

举个例子，假设 q 是 100, 然后有如下任务队列。

A ( 150 ) - B ( 80 ) - C ( 200 ) - D ( 200 )

首先 A 被处理 100 ms，然后带着剩余的 50 ms 移动至队尾。

B ( 80 ) - C ( 200 ) - D ( 200 ) - A ( 50 )

随后 B 被处理 80 ms，在总计第 180 ms 时完成处理，从队列中消失。

C ( 200 ) - D ( 200 ) - A ( 50 )

接下来 C 被处理 100 ms, 然后带着剩余的 100 ms 移动至队尾。

D ( 200 ) - A ( 50 ) - C ( 100 )

之后同理，一直循环到处理完所有任务。请编写一个程序，模拟循环调度法。

原生队列

我们可以用存放（管理）任务的队列来模拟循环调度法。首先，将初始状态的任务按顺序存入队列，然后从队头取任务，最多进行一个时间片的处理，再将仍需更多处理（时间）的任务重新添加至队列，如此循环直至队列为空。

这里要向各位介绍一下如何用数组实现一个存放整型数据的队列。用数组实现队列主要需要以下变量和函数（图 4.5 )。

用来存放数据的一维整型数组：Q
enqueue 来的数据存放在数组 Q 的各元素中。需要根据问题内容保证足够的内存空间。图 4.5 是已存入数个元素的情况
用作队头指针的整型变量：head
指示队列开头位置的变量。dequeue 会取出所指的元素。请注意，队头元素的下标不总是 0
用作队尾指针的整型变量：tail
指示队列末尾 + 1 是哪个位置（最后一个元素的后一个位置）的变量。tail 所指的位置就是要添加新元素的位置。head 与 tail 夹着的部分（不包含 tail 所指的元素）是队列的内容
向队列添加新元素 x 的函数：enqueue(x)
将 x 代入，然后 tail 加 1
从队列开头取出元素的函数：dequeue()
返问 Q[head] 的值，然后 head 加 1

下面我们来看看实际操作队列时的样子。图 4.6 演示了队列中值的添加和取出：

当 head 和 tail —致时队列为空，但此时这两个变量不一定为 0。每执行一次 enqueue(x)，新元素就会加人到 tail 的位置，然后 tail 增加 1。执行 dequeue() 则会返回 head 所指的元素，然后 head 加 1。

用数组实现队列会出现图 4.6 所示的情况，随着数据不断进出，head 与 tail 之间的队列主体部分会逐渐向数组末尾（图的右侧）移动。这样一来，tail 和 head 很快会超出数组的容量上限。如果 tail 超出数组下标上限即判定为向上溢出，那么整个数组中会有相当大的一部分空间被白白浪费掉。然而，若想防止这一情况需要让 head 时常保持在 0, 即每次执行完 dequeued() 之后让数据整体向数组开头（左侧）移动，但每次移动都会增加 $O(n)$ 的复杂度。

为应对这个问题，我们可以把构成队列的数组视为环形缓冲区来管理数据。

环形缓冲区由一维数组构成，指示队列范围的 head 和 tail 指针在超出数组范围时重新从数组开头开始循环。也就是说，如果指针加 1 之后超出了数组范围，就重新置为 0。

图 4.7 模拟了在一个已存有若干数据的队列中存取数据时的情况。执行 enqueue(1) 向队列中添加 1 时，tail 的值 7 + 1 = 8 超出了数组范围，因此将 tail 重置为 0。如果按照顺时针方向观察环形缓冲区，那么队列中的现存数据按照的顺序排列。另外，为区分队列的空与满，我们规定 tail—> head 之间至少要有一个空位。

由数组构成的队列可通过以下方法实现。

initialize()
    head = tail = 0

isEmpty()
    return head == tail
    
isFull()
    return head == (tail + 1) % MAX
    
enqueue(x)    
    if isFull()
        error(上溢)
    Q[tail] = x
    if tail + 1 == MAX
        tail = 0
    else
        tail++
        
dequeue()
	if isEmpty()
        error(下溢)
    x = Q[head]
    if head + 1 == MAX
        head = 0
    else
        head++
    return x

initialize 函数用来将 head 和 tail 设为相同值，从而清空队列
isEmpty 函数负责检查 head 和 tail 的值是否相等，以判断队列是否为空
isFull 函数用于检查队列是否已满。举个例子，假设我们使用了长度为 MAX 的 0 起点数组，那么当 head 与（tail + 1) % MAX 相等时，队列就是满的。这里 a%b 代表 a 除以 b 的余数
enqueue 函数用于在 tail 所指的位置添加 x。由于元素数增加了 1，所以 tail 也随之加 1。此时 tail 如果超过了数组容量上限（MAX - 1) 则重置为 0。另外，当队列为满时进行报错处理
dequeue 函数会将 head 所指的队头元素暂时存入变量 x，随后加 1 并返回 x 的值。此时如果超过了数组容量上限（MAX - 1 ) 则重置为 0。另外，当队列为空时进行报错处理。

用数组实现队列时，关键在于如何有效利用内存，以及如何将 enqueue 和 dequeue 的算法复杂度控制在 $O (1)$。实际上，只要使用环形缓冲区，就可以同时以复杂度 $O(1)$ 实现 enqueue 和 dequeue 的操作。

#include <iostream>
#include <string>
using namespace std;

#define MAX 100005

struct task {
    string name;
    int time;
};

int head, tail, n, q;
task Q[MAX];

void enqueue(task x) {
    Q[tail] = x;
    tail = (tail + 1) % MAX;
}

task dequeue() {
    task x = Q[head];
    head = (head + 1) % MAX;
    return x;
}

int main(){
    int cost, sum = 0;
    task t;
    cin >> n >> q;

    for (int i = 0; i < n; ++i) {
        cin >> Q[i].name >> Q[i].time;
    }

    head = 0;
    tail = n;

    while (head != tail) {
        t = dequeue();
        cost = min(q, t.time);
        t.time -= cost;
        sum += cost;
        if (t.time > 0)
            enqueue(t);
        else
            cout << t.name << " " << sum << endl;
    }

    return 0;
}

标准库

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int main(){
    int n, q, key, cost, sum = 0;
    string name;
    cin >> n >> q;
    queue<pair<string, int>> Q;

    for (int i = 0; i < n; ++i) {
        cin >> name >> key;
        Q.push(make_pair(name, key));
    }

    pair<string, int> u;
    while (!Q.empty()) {
        u = Q.front();
        Q.pop();

        cost = min(q, u.second);
        u.second -= cost;
        sum += cost;
        
        if (u.second > 0) 
            Q.push(u);
        else
            cout << u.first << " " << u.second << endl;
    }


    return 0;
}

pair 是保存成对数值的结构体模板，声明时需要在 < > 中指令两个数据类型。make_pair 用于生成一对数值，第 1 个元素通过 first 访问，第 2 个元素通过 second 访问。

ALDS1_3_C Doubly Linked List

Your task is to implement a double linked list.

Write a program which performs the following operations:

insert x: insert an element with key x into the front of the list.
delete x: delete the first element which has the key of x from the list. If there is not such element, you need not do anything.
deleteFirst: delete the first element from the list.
deleteLast: delete the last element from the list.

Input

The input is given in the following format:

n
command1
command2
…
commandn

In the first line, the number of operations n is given. In the following n lines, the above mentioned operations are given in the following format:

insert x
delete x
deleteFirst
deleteLast

Output

Print all the element (key) in the list after the given operations. Two consequtive keys should be separated by a single space.

Constraints

The number of operations ≤ 2,000,000
The number of delete operations ≤ 20
0 ≤ value of a key ≤ $10^9$
The number of elements in the list does not exceed $10^6$
For a delete, deleteFirst or deleteLast operation, there is at least one element in the list.

Sample Input 1

7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5

Sample Output 1

6 1 2

Sample Input 2

9
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5
deleteFirst
deleteLast

Sample Output 2

問題を解く

某些数据结构需要满足数据的动态变化。在实现它们的时候，编程者需要具备适时申请或释放内存的技巧。

这里，本书特地使用 C++ 程序实现双向链表的操作，通过对其代码的讲解，向各位具体说明内存申请和链表更改的相关知识。

原生链表

如图 4.8 所示，表中的各元素称作 “结点”。双向链表的结点是结构体，由数据本体（这里是整数 key ), 指向前一元素的指针 prev 以及指向后一元素的指针 next 组成，这些结构体通过指针连接成一个链，就形成了双向链表。

struct Node {
	int key;
	Node *prev, *next;
}

另外，在表头设置一个特殊结点可以简化链表的实现。我们将这个结点称为 “头结点”。头结点中虽然不包含实际数据，但它可以让我们更轻松地对链表做更改。比如，加入头结点之后，我们将更容易实现删除元素的操作。

init 函数用于初始化链表，如图 4.9 所示，它会生成一个 NIL 结点（编程语言中，NIL 和 NULL 这两个值表示 “空”，虽然在不同语言中其内容有所差异，但本书中的 NIL 意义为 “空”，同时还作为保存 “不存在的编号” 等数据的变量来使用）作为链表的尖结点, 然后让 prev 和 next 都指向这个头结点，从而创建一个空表。

void insert(int key) {
    Node *x = (Node*)malloc(sizeof(Node));
    x->key = key;
    
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

listSearch 函数用于搜索元素，它可以在链表中寻找包含指定键值的结点，并返回其指针。假设 cur 为指向当前位置结点的指针，那么只要从头结点的 next 所指的结点，即链表开头的元素汗始逐个执行 cur = cur -> next，即可逐一访问每个结点。

Node* listSearch() {
	Node *cur = nil->next;
    while(cur != nil && cur->key != key) {
        cur = cur -> next;
    }
    return cur;
}

在访问过程中发现 key 或者指针回到头结点 NIL 时结朿搜索，并返回此时 cur 的值。

deleteNode 函数会通过如图 4.11 所示的步骤改变指针所指的位置，从而删除指定结点 t。在 C++ 中，我们必须手动释放已删除结点的内存。这里的 free 是 C 语言标准库中的函数，用于释放已不需要的内存空间。

void deleteNode(Node *t) {
    if (t == nil) return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

void deleteFirst() {
    deleteNode(nil->next);
}

void deleteLast() {
    deleteNode(nil->prev);
}

void deleteKey(int key) {
    deleteNode(listSearch(key));
}

deleteFirst 函数、deleteLast 函数分别用于删除头结点 next 、prev 所指向的结点。

deleteKey 函数可以删除包含指定 key 的结点，它会先通过 listSearch 函数搜索出 key —致的结点 t，然后再使用 deleteNote(t) 删除该结点。

往双向链表中添加元素时，只需要更改几个指针的指向，因此算法复杂度为 $O(1)$。

数组访问 A[i] 所消耗的时间固定，但表需要通过指针一步步寻找元素。因此当表中含有 N 个元素时，搜索算法的复杂度为 $O(N)$。

删除双向链表开头或末尾的元素仅需 $O(1)$ 的复杂度，但删除包含特定 key 的元素时需要按顺序遍历链表，所以算法复杂度为 $O(N)$。

这里介绍的链表的实现方法中，由于搜索和删除的算法复杂度都高达 $O(N)$ , 因此对单个链表来说实用价值不大。但是，它们在之后的章节中将作为其他数据结构的零部件（或者实现其他数据结构所需的知识）出现并发挥作用。

#include <iostream>
#include <cstdio>

struct Node {
    int key;
    Node *prev, *next;
};

Node* nil;
void init() {
    nil = new Node;
    nil->prev = nil;
    nil->next = nil;
}

void insert(int key) {
    Node* x = new Node;
    x->key = key;
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

Node* listSearch(int key) {
    Node* cur = nil->next;
    while (cur != nil && cur->key != key) {
        cur = cur->next;
    }
    return cur;
}

void deleteNode(Node* t) {
    if (t == nil) return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    delete t;
}

void deleteFirst() {
    deleteNode(nil->next);
}

void deleteLast() {
    deleteNode(nil->prev);
}

void deleteKey(int key) {
    deleteNode(listSearch(key));
}

void printList() {
    Node* cur = nil->next;
    int isFirst = 0;
    while (true) {
        if (cur == nil) break;
        if (isFirst++ > 0) std::cout << " ";
        std::cout << cur->key;
        cur = cur->next;
    }
    std::cout << std::endl;
}

int main(){
    int n, key;
    char cmd[20];

    std::cin >> n;
    init();
    for (int i = 0; i < n; ++i) {
        scanf("%s", cmd);
        if (cmd[6] == 'F')
            deleteFirst();
        else if (cmd[6] == 'L')
            deleteLast();
        else {
            scanf("%d", &key);
            if (cmd[0] == 'i')
                insert(key);
            else if (cmd[0] == 'd')
                deleteKey(key);
        }
    }

    printList();
    delete nil;

    return 0;
}

这里的输入出现了一点小小的问题，原书是这样写的：

init();
for(i = 0; i < n; i++) {
	scanf("%s%d", cmd, &key);
    if (cmd[0] == 'i')
        insert(key);
    else if (cmd[0] == 'd') {
        if (strlen(cmd) > 6) {
            if (cmd[6] == 'F')
                deleteFirst();
            else if (cmd[6] == 'L')
                deleteLast();
            else
                deleteKey(key);
        }
    }
}

后面不知道哪里出了问题，改了一下输入的逻辑就ok了：

init();
for (int i = 0; i < n; ++i) {
	scanf("%s", cmd);
	if (cmd[6] == 'F')
		deleteFirst();
	else if (cmd[6] == 'L')
		deleteLast();
	else {
		scanf("%d", &key);
		if (cmd[0] == 'i')
			insert(key);
		else if (cmd[0] == 'd')
			deleteKey(key);
	}
}

标准库

list 既可以像 vector —样通过“[ ]”运算符直接访问特定元素，也可以用迭代器逐个进行访问另外，list 还具备一项 vector 所不具备的特长，那就是元素的插入与删除操作只需 $O(1)$ 即可完成，效率极高。现在我们用 STL 的 list 来解之前的例题3 ALDS1 _3_C: Doubly Linked List 可以通过下述方法实现：

#include <iostream>
#include <cstdio>
#include <list>
using namespace std;

int main(){
    int n, key;
    char cmd[20];
    list<int> v;
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%s", cmd);
        if (cmd[0] == 'i') {
            scanf("%d", &key);
            v.push_front(key);
        } else if (cmd[6] == 'F') {
            v.pop_front();
        } else if (cmd[6] == 'L') {
            v.pop_back();
        } else if (cmd[0] == 'd') {
            scanf("%d", &key);
            for (list<int>::iterator it = v.begin(); it != v.end(); ++it) {
                if (*it == key) {
                    v.erase(it);
                    break;
                }
            }
        }
    }
    
    int isFirst = 0;
    for (list<int>::iterator it = v.begin(); it != v.end(); ++it) {
        if (isFirst++) cout << " ";
        cout << *it;
    }
    cout << endl;

    return 0;
}

ALDS1_3_D Areas on the Cross-Section Diagram

Your task is to simulate a flood damage.

For a given cross-section diagram, reports areas of flooded sections.

Assume that rain is falling endlessly in the region and the water overflowing from the region is falling in the sea at the both sides. For example, for the above cross-section diagram, the rain will create floods which have areas of 4, 2, 1, 19 and 9 respectively.

Input

A string, which represents slopes and flatlands by ‘/‘, ‘\‘ and ‘_‘ respectively, is given in a line. For example, the region of the above example is given by a string:

Output

Report the areas of floods in the following format:

$A$
$k L_1 L_2 … L_k$

In the first line, print the total area $A$ of created floods.

In the second line, print the number of floods $k$ and areas $L_i(i=1,2,…,k)$ for each flood from the left side of the cross-section diagram. Print a space character before $L_i$.

Constraints

1≤ length of the string ≤20,000

Sample Input 1

\\//

Sample Output 1

4
1 4

Sample Input 2

\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\

Sample Output 2

35
5 4 2 1 19 9

問題を解く

为给某地区制订防洪策略，我们要模拟洪水时的受灾状况。如上图所示，现已在 1 X 1( $m^2$ ) 的网格纸上画出了该地区的地形断面图，请报告该地区各积水处的横截面积。

假设给定地区持续降雨，从该地区溢出的多余雨水将流人左右的海中。以上图中的断面图为例，积水处的横截面积从左至右分别为 4、2、1、19。

本题的解法有很多，比如运用排序算法。不过在这里，我们要考虑如何用栈实现题目需求。

首先，我们通过下述算法求总面积（第 1 个输出数据）。

对输入的字符 $s_i$ 进行逐个检查：

如果是 “\”，则将表示该字符位置（从开头数第几个字符）的整数 $i$ 压人栈S1
如果是 “/”，则从栈 S1 顶部取出与之对应的 “\”的位置 $i_p$, 算出二者的距离 $i-i_p$ 并累加到总面积里

字符 “_” 的作用只是将一对 “\” 与 “/” 的距离加 1 ，因此我们从栈中取出 “\” 时可以直接与对应的 “/”计算距离，不必考虑 “_”。

接下来是求各积水处面积的算法。

我们另建一个栈 S2 来保存各积水处的面积。栈 S2 中的每个元素包含一对数据，分別是 “该积水处最左侧 “\” 的位置” 和 “该积水处当前的面积”。例如图 4.12 中，i 表示当前 “/” 表示当前 “/” 的位置，表示与之相对应的 “\” 的位置，S2 中存放着（ j +1，5 ) 和 ( k, 4 ) 两个积水处的面积。

接下来，新形成的面积 = 当前 S2 中的两个面积之和 + 新形成的 i - j 部分的面积。这里我们要从 S2 中取出被引用的（多个）面积，再将新算出的面积压入 S2。

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int sum = 0;
    char ch;
    stack<int> s1;
    stack<pair<int, int> > s2;
    for (int i = 0; cin >> ch; ++i) {
        if (ch == '\\') {
            s1.push(i);
        } else if (ch == '/' && s1.size() > 0) {
            int j = s1.top();
            s1.pop();
            sum += i - j;

            int area = i - j;
            while (s2.size() > 0 && s2.top().first > j) {
                area += s2.top().second;
                s2.pop();
            }
            s2.push(make_pair(j, area));
        }
    }

    vector<int> ans;
    while (s2.size() > 0) {
        ans.push_back(s2.top().second);
        s2.pop();
    }
    reverse(ans.begin(), ans.end());

    cout << sum << endl;
    cout << ans.size();
    for (int i = 0; i < ans.size(); ++i) {
        cout << " ";
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

Topic # 4 Search

搜索（或检索）是指从数据集合中找岀目标元素的处理。与排序相同，搜索的各元素通常也由多个项目组成。不过，本章例题中使用的数据相对简单，多以值作为关键字。

所谓搜索，就是在数据集合中寻找给定关键字的位置或判断其有无，比如 “数列 {8,13,5, 7,21,1} 中 7 位于第几位?” 等。基本的搜索算法有如下二种，分别为线性搜索、二分搜索、散列法。

线性搜索

线性搜索就是从数组开头顺次访问各元素，检查该元素是否与目标值相等。一旦相等则返回该元素的位置并结束搜索。如果检查到数组末尾仍未发现目标值，则返回一个特殊值来说明该情况。线性搜索的算法效率很低，但适用于任何形式的数据。

二分搜索

二分搜索（二分查找）算法可以利用数据的大小进行高速搜索。很多时候，计算机管理数据时会根据特定项目对其进行排序，这就让二分搜索算法有了用武之地。

假设数组中存放的数据已按关键字升序排列，那么对其使用二分搜索算法时思路如下

将整个数组作为搜索范围
检查位于搜索范围正中央的元素
如果中央元素的关键字与目标关键字一致则结束搜索
如果中央元素的关键字小于目标关键字，则以前半部分为搜索范围重新执行 2; 如果大于目标关键字，则以后半部分为搜索范围重新执行 2。

二分搜索每执行完一步搜索范围都会减半，因此可以在极短时间内完成搜索。

散列法

在散列法中，各元素的存储位置由散列函数决定。散列既是一种数据结构，同时也是一种使用散列表的算法。这种算法只需将元素的关键字（值）代入特定函数便可找岀其对应位置，对某些种类的数据有着极高的搜索效率。

ALDS1_4_A Search I

You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.

Input

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.

Output

Print C in a line.

Constraints

n ≤ 10000
q ≤ 500
0 ≤ an element in S ≤ $10^9$
0 ≤ an element in T ≤ $10^9$

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

問題を解く

请编写一个程序，输入包含 $n$ 个整数的数列 S 以及包含 q 个不重复整数的数列 T，输出既包含于 T 也包含于 S 的整数的个数 C。

我们通过线性搜索来检查数列 S 中是否包含 T 的各元素。线性搜索可以用 for 循环来实现，具体过程如下。

linearSearch()
	for i from 0 to n - 1
		if A[i] == key
            return i
    return NOT_FOUND

向线性搜索中引入“标记”可以将算法效率提高常数倍。所谓标记，就是我们在数组等数据结构中设置的一个拥有特殊值的元素。借助这项编程技巧，我们能达到简化循环控制等诸多目的。在线性搜索中，我们可以把含有目标关键字的数据放在数组末尾，用作标标记。具体操作如图 5.1 所示。

含有标记的线性搜索可以用如下方法实现。

linearSearch()
	i = 0
    A[n] = key
    while A[i] 与 key 不同
        i++
    if i 到达了 n
        return NOT_FOUND
	return i

Program 5.1 与 Program 5.2 的区别在于主循环中比较运算的次数。Program 5.1 需要两个比较运算，一个是 for 循环的结束条件（比如C语言中 for (i = 0;i < n;i++) ），另一个是关键字之间的比较。相对地，Program 5.2 只需要一个不等价运算即可。由于标记能确保 while 不成为死循环，因此可以省去循环结束条件。

线性搜索的算法复杂度为 $O(n)$，但在引入标记之后效率能提升常数倍，处理大规模数据时会有比较明显的效果。

解本题 (ALDS1_4 A: Linear Search ) 时，总共要对具有 $n$ 个元素的数组进行 $q$ 次线性搜索，算法复杂度为 $O(qn)$。

#include <iostream>
#include <vector>
using namespace std;

bool linearSearch(vector<long> s, int key) {
    int i = 0;
    s[s.size()] = key;
    while (s[i] != key) i++;
    return i != s.size();
}

int main(){
    long input;
    int n, q, count = 0;
    vector<long> s;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> input;
        s.push_back(input);
    }

    cin >> q;
    for (int j = 0; j < q; ++j) {
        cin >> input;
        if (linearSearch(s, input)) count++;
    }

    cout << count << endl;
    return 0;
}

ALDS1_4_B Search II

You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.

Input

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.

Output

Print C in a line.

Constraints

Elements in S is sorted in ascending order
n ≤ 100000
q ≤ 50000
0 ≤ an element in S ≤ 109
0 ≤ an element in T ≤ 109

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

問題を解く

本题的思路与上一题基本相同，都是通过搜索检查数列 S 中是否包含 T 的各个元素。但是，$O(n)$ 的线性搜索无法在限制时间之内完成处理。本题我们要有效利用 “S 的元素按升序排列” 这一限制条件，采用二分搜索解题。

假设有一个包含 $n$ 个元素的数组 $A$，我们要用二分搜索在其中寻找 key，其算法伪代码如下。

binarySearch(A, key)
	left = 0
    right = n
    while left < right
        mid = (left + right)/2
        if A[mid] == key
            return mid
        else if A[mid] > key
            right = mid
		else
            left = mid + 1
	return NOT_FOUND

在 while 循环中，先通过 ( left +right ) /2 求出当前搜索范围的中间位置 mid，再将 mid 所指的元素 A[mid] 与 key 进行比较，如果一致则返回 mid。当 key 小于 A[mid] 时，证明目标值位于 mid 前方，所以把 mid 赋给 right，将搜索范围收缩至前半部分。反之则把 mid+1 赋给 left，将搜索范围收缩至后半部分。上面例子的第一步中，key ( = 36) 比中间值 A[mid] 更大，所以将 left 设置为8 (搜索 8 之前的元素没有意义)。

while 的循环条件 left < right 表示搜索范围仍不为空。如果搜索范围为空，就代表数组中没有找到 key，返回 NOT_FOUND。

对含有 $n$ 个元素的数组执行线性搜索以及二分搜索时，最坏的情况下的比较运算的次数分别如下表所示。

元素数	线性搜索	二分搜索
100	100	7
10000	10000	14
1000000	1000000	20

线性搜索在最坏情况下要比较 $n$ 次，二分搜索大概需要 $\log_2{n}$ 次。由于二分搜索每进行一次比较搜索范围就会减半，因此很容易推导出其计算效率为 $O(\log{n})$。

本题 ( ALDS1_4_C: Binary Search ) 需要以 $T$ 的各元素为 key 进行二分搜索，即解题算法复杂度为 $O(q\log{n})$。

本题的输入数据已经完成了排序，今后当我们遇到无序的数据时，只要预先进行一次排序，就可以套用二分搜索了。总而言之，“排序之后即可使用二分搜索”的思路可以应用到诸多问题之中。不过，考虑到数据的体积，绝大多数情况下都需要用到高等排序算法（我们将在第 7 章详细学习）。

#include <iostream>
using namespace std;

bool binarySearch(long A[], int n, int key) {
    int left = 0;
    int right = n;

    while (left < right) {
        int mid = (left + right) / 2;
        if (A[mid] == key)
            return true;
        else if (A[mid] > key)
            right = mid;
        else
            left = mid + 1;
    }
    return false;
}

int main(){
    long input;
    int n, q, count = 0;
    long A[1000000];

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    cin >> q;
    for (int j = 0; j < q; ++j) {
        cin >> input;
        if (binarySearch(A, n, input)) count++;
    }

    cout << count << endl;
    return 0;
}

ALDS1_4_C Search III

Your task is to write a program of a simple dictionary which implements the following instructions:

insert str: insert a string str in to the dictionary
find str: if the distionary contains str, then print ‘yes’, otherwise print ‘no’

Input

In the first line n, the number of instructions is given. In the following n lines, n instructions are given in the above mentioned format.

Output

Print yes or no for each find instruction in a line.

Constraints

A string consists of ‘A’, ‘C’, ‘G’, or ‘T’
1 ≤ length of a string ≤ 12
n ≤ 1000000

Sample Input 1

5
insert A
insert T
insert C
find G
find A

Sample Output 1

no
yes

Sample Input 2

13
insert AAA
insert AAC
insert AGA
insert AGG
insert TTT
find AAA
find CCC
find CCC
insert CCC
find CCC
insert T
find TTT
find T

Sample Output 2

yes
no
no
yes
yes
yes

Notes

Template in C

問題を解く

散列法是一种搜索算法，它可以根据各元素的值来确定存储位置，然后将位置保管在散列表中，从而实现数据的高速搜索。其中散列表是一种数据结构，能对包含关键字的数据集合高效地执行动态插入、搜索、删除操作。虽然链表也能完成同样操作，但搜索和删除的复杂度都高达 $O(n)$。

散列表由容纳 m 个元素的数组 T 以及根据数据关键字决定数组下标的函数共同组成。也就是说，我们要将数据的关键字输入该函数，由该函数决定数据在数组中的位置，散列表大致可通过以下方法实现。

insert(data)
	T[h(data.key)] = data

search(data)
    return T[h(data.key)]

这里我们假设散列函数的输人值 data.key 为整数。请注意，当关键字为字符串等其他类型时，需要借助某些手法将其转换为相应的整数。

这里的 $h(k)$ 是根据 $k$ 值求数组 $T$ 下标的函数，称为散列函数。另外，该函数的返回值称为散列值。散列函数求出的散列值范围在 0 到 m - 1 之间（m 为数组 T 的长度）。为满足这一条件，函数内需要使用取余运算，保证输出值为 0 到 m - 1 之间的整数，比如
$$
h(k) = k \space mod \space m
$$
就是一种散列函数（这里 a mod b 是指 a 除以 b 所得的余数）。不过，如果单有这一个运算，会发生不同 key 对应同一散列值的情况，即出现“冲突”。

开放地址法是解决这类冲突的常用手段之一。这里向各位介绍的是双散列结构中使用的开放地址法。如下所示，在双散列结构中一旦出现冲突，程序会调用第二个散列函数来求散列值。
$$
H(k) = h(k, i)=(h_1(k) + i \times h_2(k)) \space mod \space m
$$
散列函数 $h(k,i)$ 拥有关键字 $k$ 和整数 $i$ 两个参数，这里的 $i$ 是发生冲突后计算下一个散列值的次数。也就是说，只要散列函数 $H(k)$ 起了冲突，就会依次调用 $h(k,0)$、$h(k,1)$、$h(k,2)$…，直到不发生冲突为止，然后返回这个 $h(k,i)$ 的值作为散列值。如图5.4所示，该算法先通过 $h_1(k)$ 求出第一个下标，然后在发生冲突时将下标移动 $h_2(k)$ 个位置，从而寻找仍然空着的位置。

要注意的是，因为下标每次移动 $h(k)$ 个位置，所以必须保证 $T$ 的长度 $m$ 与 $h_2(k)$ 互质，否则会出现无法生成下标的情况。这种时候，我们可以特意让 $m$ 为质数，然后取一个小于 $m$ 的值作为 $h_2(k)$，从而避免上述情况发生。

比如，散列法可以通过下述方法实现。

h1(key)
	return key mod

h2(key)
	return 1 + (key mod (m - 1))

h(key, i)
	return (h1(key) + i * h2(key)) mod m
    
insert(T, key)
    i = 0
    while true
        j = h(key, i)
        if T[j] == NIL
            T[j] = key
            return j
        else    
            i++
      
search(T, key)
	i = 0
    while true
        j = h(key, i)
        if T[j] == NIL
            return j
        else if T[j] == NIL or i >= m
            return NIL
        else
            i++

上述伪代码中，我们用 $T[j]$ 是否为 NIL 来判断当前位置是否为空。

如果忽略发生冲突的情况，散列法插入和搜索元素的算法复杂度仅为 $O(1)$。散列函数根据其用途不同会用到各种算法（比如加密技术），有时还会用到启发式计算式。本书在编写前已经对基本的散列函数及其机制进行了验证。

#include<cstdio>
#include<cstring>

#define M 1046527
#define L 14

char H[M][L];

int getChar(char ch){
    if (ch == 'A') return 1;
    else if (ch == 'C') return 2;
    else if (ch == 'G') return 3;
    else if (ch == 'T') return 4;
    else return 0;
}

long long getKey(char str[]){
    long long key = 0, p = 1;
    for (long long i = 0; i < strlen(str); i++){
        key += p*(getChar(str[i]));
        p *= 5;
    }
    return key;
}

int h1(int key) { 
    return key % M; 
}

int h2(int key) { 
    return 1 + (key % (M - 1)); 
}

int hash(int key, int i) { 
    return (h1(key) + i * h2(key)) % M;
}

int find(char str[]) {
    long long key, h;
    key = getKey(str);
    for (long long i = 0;; i++) {
        h = hash(key, i);
        if(strcmp(H[h],str) == 0) 
            return 1;
        else if (strlen(H[h]) == 0) 
            return 0;
    }
    return 0;
}

int insert(char str[]) {
    long long key, h;
    key = getKey(str);
    for (long long i = 0; ; i++) {
        h = hash(key, i);
        if( strcmp(H[h],str) == 0 ) return 1;
        else if ( strlen(H[h]) == 0 ) {
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}


int main() {
    int i, n, h;
    char str[L], cmd[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    for ( i = 0; i < n; i++ ) {
        scanf("%s %s", cmd, str);

        if (cmd[0] == 'i')
            insert(str);
        else if (find(str))
            printf("yes\n");
        else
            printf("no\n");
    }
}

ALDS1_4_D Allocation

You are given $n$ packages of $w_i$ kg from a belt conveyor in order ($i=0,1,…n−1$). You should load all packages onto $k$ trucks which have the common maximum load $P$. Each truck can load consecutive packages (more than or equals to zero) from the belt conveyor unless the total weights of the packages in the sequence does not exceed the maximum load PP.

Write a program which reads $n$, $k$ and $w_i$, and reports the minimum value of the maximum load $P$ to load all packages from the belt conveyor.

Input

In the first line, two integers $n$ and $k$ are given separated by a space character. In the following nn lines, $w_i$ are given respectively.

Output

Print the minimum value of $P$ in a line.

Constraints

1 ≤ $n$ ≤ 100,000
1 ≤ $k$ ≤ 100,000
1 ≤ $w_i$ ≤ 10,000

Sample Input 1

Sample Output 1

If the first truck loads two packages of {8,1}, the second truck loads two packages of {7,3} and the third truck loads a package of {9}, then the minimum value of the maximum load $P$ shall be 10.

Sample Input 2

Sample Output 2

If the first truck loads three packages of {1,2,2} and the second truck loads a package of {6}, then the minimum value of the maximum load $P$ shall be 6.

問題を解く

传送带依次送来了重量分别为 $w_i$($i=0,1,⋯，N -1$) 的 $n$ 个货物。现在要将这些货物装到 $k$ 辆卡车上。每辆卡车可装载的货物数大于等于0, 但货物重量总和不得超过卡车的最大运载量 $P$。所有卡车的最大运载量 $P$ —致。

请编写一个程序，输入 $n$、$k$、$w_i$，求出装载全部货物所需的最大运载量 $P$ 的最小值。

确定最大运载量 $P$ 时，首先要编写一个算法来计算 $k$ 辆以内的卡车总共能装多少货物。思路很简单，只要卡车的运载量没达到 $P$，我们就让其继续按顺序装货物，最后再计算所有卡车运载量的总和即可。这里我们以 $P$ 为实参，编写一个返回可装载货物数 $v$ 的函数 $v = f(P)$。这个函数的算法复杂度为 $O(n)$。

现在我们只需要调用这个函数，让 $P$ 从 0 开始逐渐自增，第一个让 $v$ 大于等于 $n$ 的 $P$ 就是答案。但是，逐个检查 $P$ 会使算法复杂度达到 $O(Pn)$，结合问题的限制条件来看，程序不可能在限制时间内完成处理。

这里我们利用 “$P$ 增加则 $v$ 也增加” （严格来说是 $P$ 增加时会减少）的性质，用二分搜索来求 $P$。二分搜索可以将算法复杂度降低至 $( n\log P)$。

#include <iostream>
using namespace std;

#define MAX 100000

int n, k;
long long w[MAX];

int check(long long p) {
    int i = 0;
    for (int j = 0; j < k; ++j) {
        long long s = 0;
        while (s + w[i] <= p) {
            s += w[i];
            i++;
            if (i == n) return n;
        }
    }
    return i;
}

int solve() {
    long long left = 0;
    long long right = 100000 * 10000;
    long long mid;

    while (right - left > 1) {
        mid = (left + right) / 2;
        int v = check(mid);
        if (v >= n) right = mid;
        else left = mid;
    }
    return right;
}

int main() {
    cin >> n >> k;
    long long P;
    for (int i = 0; i < n; ++i)
        cin >> w[i];

    long long ans = solve();
    cout << ans << endl;
}

Topic # 5 Recursion / Divide and Conquer

将问题分解，通过求解局部性的小问题来解开原本的问题这种技巧称为分治法，我们在很多算法中都能看到。实现分治法需要用到递归。本章就将带领各位求解分治法以及递归的相关问题

使用递归的技巧，可以将一个问题拆分成两个或更多较小的局部问题，利用递归函数求出每个局部问题的解，然后再将结果整合，最终解决原问题。这种编程手法称为分治法( Divide and Conquer ), 其算法实现的步骤如下。

将问题“分割”成局部问题（Divide）
递归地求解局部问题（Solve）
将局部问题的解“整合”，解决原问题

举个例子，数组 A 中最大的元素既可以用线性搜索来查找，也可以如 Program 6.2 所示用分治法来查找。这里的函数 findMaximum(A, 1, r) 表示在数组 A 的 l 到 r （不包含 r）的范围内查找最大元素。

findMaximum(A, l, r)
	m = (l + r)/2
	if l == r - 1
		return A[l]
	else
    	u = findMaximum(A, l, m)
    	v = findMaximum(A, m, r)
    	x = max(u, v)
    return x

ALDS1_5_A Exhaustive Search

Write a program which reads a sequence A of n elements and an integer M, and outputs “yes” if you can make M by adding elements in A, otherwise “no”. You can use an element only once.

You are given the sequence A and q questions where each question contains $M_i$.

Input

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers ($M_i$) are given.

Output

For each question $M_i$, print yes or no.

Constraints

n ≤ 20
q ≤ 200
1 ≤ elements in A ≤ 2000
1 ≤ $M_i$ ≤ 2000

Sample Input 1

5
1 5 7 10 21
8
2 4 17 8 22 21 100 35

Sample Output 1

no
no
yes
yes
yes
yes
no
no

Notes

You can solve this problem by a Burte Force approach. Suppose solve(p, t) is a function which checkes whether you can make t by selecting elements after p-th element (inclusive). Then you can recursively call the following functions:

solve(0, M)
solve(1, M-{sum created from elements before 1st element})
solve(2, M-{sum created from elements before 2nd element})
…

The recursive function has two choices: you selected p-th element and not. So, you can check solve(p+1, t-A[p]) and solve(p+1, t) in solve(p, t) to check the all combinations.

For example, the following figure shows that 8 can be made by A[0] + A[2].