---
tags: teachcpp
author: qpoiPeng
---

# 2021 Spring G7 Week 11 講義
[toc]

## 重要事項 - 考試
下下禮拜要進行大會考！
下下禮拜要進行大會考！
下下禮拜要進行大會考！

考試時間：兩小時（具體時程之後宣布）
考試內容：四題程式題，使用 Zero Judge。
考試範圍：上下學期所有內容都有可能出現，遞迴不會考，放心。

## Homework Solution
### c381.

#include<iostream>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  while (n != 0 && m != 0) {
    string s, tmp;
    for (int i = 0; i < n; ++i) {
      cin >> tmp;
      s += tmp;
    }
    string ans;
    for (int i = 0; i < m; ++i) {
      int index;
      cin >> index;
      ans += s[index - 1];
    }
    cout << ans << '\n';
    cin >> n >> m;
  }
}

### f312.

#include<iostream>
using namespace std;

struct Factory {
  int A, B, C;
  int cal(int x) {
    return A * x * x + B * x + C;
  }
};

int main() {
  Factory f1, f2;
  int n;
  cin >> f1.A >> f1.B >> f1.C;
  cin >> f2.A >> f2.B >> f2.C;
  cin >> n;
  int ans = -2147483648;
  for (int i = 0; i <= n; ++i) {
    int temp = f1.cal(i) + f2.cal(n - i);
    ans = ans > temp? ans : temp;
  }
  cout << ans << '\n';
}

## sort 函式介紹
今天要跟大家介紹一個 C++ 很常用到的函式，`sort()`。

我們寫程式有時候會需要對一些資料排序，但我們以前教的 selection sort 自己寫起來很麻煩，而且時間複雜度是 $O(n^2)$，太慢了。所以，C++ 其實有寫好的 sort 可以讓你直接用！真是太棒了對吧？我們這就來看怎麼用。

#include<iostream>
#include<algorithm>    // 用 sort 要這個
using namespace std;

int main() {
  int intArray[10] = {5, 4, 3, 2, 8, 7, 6, 1, 0, 9};
  double doubleArray[5] = {3.3, 2.2, 8.8, 2.5, 1.9};
  
  cout << "Before sort :\n\n";
  for (int i = 0; i < 10; ++i)
    cout << intArray[i] << ' ';
  cout << "\n\n";
  for (int i = 0; i < 5; ++i)
    cout << doubleArray[i] << ' ';
  cout << "\n\n";
  
  sort(intArray, intArray + 10);
  sort(doubleArray, doubleArray + 5);
  
  cout << "\nAfter sort :\n\n";
  for (int i = 0; i < 10; ++i)
    cout << intArray[i] << ' ';
  cout << "\n\n";
  for (int i = 0; i < 5; ++i)
    cout << doubleArray[i] << ' ';
  cout << "\n\n";
}

執行結果：

這樣就排序好了！而且這樣的排序時間複雜度是 $O(n\log n)$ ，比我們自己寫的 selection sort 還要快！真是又快又好寫對吧。

在上面的例子中，`sort()` 需要兩個參數，那兩個參數都是放一個==位址==，分別代表要排序的起點跟終點。所以對一個長度為 10 的陣列 `intArray[10]` 來說，起點就是 `intArray` 終點則是 `intArray + 10`。

這邊有兩個地方要注意：
1. 因為是位址，所以終點要寫 `intArray + 10`，不能寫 `intArray[10]`。
2. 他的終點是不包含終點那個位置的。事實上，`intArray + 10` 是這個陣列第十一個元素的位置（因為位址從 0 開始算），但這邊這樣寫並不會出錯，因為他只會排序到 `intArray + 10` 前面的位址。

自己試試看！
把上面的程式碼複製下來，只透過更改 sort 裡面的參數，讓程式的輸出變成下面這樣：

其中反白的部分是他有排序好的地方，其他地方要維持不變。

接下來，大家來練習一下 f832.！

Solution :

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

int main() {
  int N, M;
  int w[100005];
  int c[100005];
  cin >> N >> M;
  for (int i = 0; i < N; ++i)
    cin >> w[i];
  for (int i = 0; i < M; ++i)
    cin >> c[i];

  sort(w, w + N);
  sort(c, c + M);

  int i = N - 1, j = M - 1;
  long long int ans = 0;
  
  while (i >= 0 && j >= 0) {
    if (w[i] <= c[j]) {
      ans += w[i];
      --i, --j;
    }
    else
      --i;
  }
  cout << ans << '\n';
}

## Challenge Time

大家應該有學過怎麼判斷一個數是不是 2, 3, 5, 11 的倍數。
請你寫一個程式，判斷輸入的是是不是這些數的倍數。

輸入：多組測資，以 EOF 結束。每組測資僅一個數字 $x$，其中 $0\le x \le 10^{100}$。
輸出：對於每組測資，輸出一行，那一行包含四個以空格格開的 yes/no，分別代表是不是 2/3/5 的倍數。

Sample Input 1 :
2
20
33
1000000000000000000000000000002

Sample Output 1 :
yes no no
yes no yes
no yes no
yes yes no

## Zero Judge Challenge
f605.
a275.（回家作業！）
a518.
a273.