第三場比賽 題解
=
>聽說吃拉麵能變強
>

# [z021](https://judge.cp.ccns.io/problem/z021)：
令 $x$ 為 $m$ 個人過來**前**，長椅上目前**佔最多**人的人數

最大的 $k$ 為 $x + m$

而對於最小的 $k$：
若先去坐 $x$ 人的那個長椅，$k$ 會變大，所以 $m$ 個人應先分配到其他長椅上
於是求除了 $x$ 人的長椅外，還**剩下**多少位置(`rem`)

for (int i = 0; i < n; i++) rem += x-a[i];

若 $m \le \text{rem}$ 則顯然 $k = x$
若 $m > \text{rem}$ 就將部份人分配到剩下的位置中(此時長椅人數都為 $x$)，
接著將剩餘的人 $m-\text{rem}$ 平均分配到每張長椅上，$k = x + \lceil {m - \text{rem}\over n} \rceil$

以下完整程式碼：

#include<bits/stdc++.h>
using namespace std;

int const maxn = 110;

int n, m, a[maxn];

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);

  int x = *max_element(a, a+n), rem = 0; // remainder
  for(int i = 0; i < n; i++) rem += x-a[i];

  if(m > rem) printf("%d ", x + (m-rem)/n + !!((m-rem)%n));
  else printf("%d ", x);

  printf("%d\n", x+m);

  return 0;
}

# [z022](https://judge.cp.ccns.io/problem/z022)：

二元二次方程式。
通常遇到方程式可以試試看「二分搜有理數」，而這題恰巧可以用上公式解。
遇到小數的時候，注意題目敘述，如果可以的話盡量多輸出幾位。

#include <bits/stdc++.h>
#define Double long double

using namespace std;

int main() {
  int T;
  cin >> T;
  while(T--) {
    Double D, a, b;
    cin >> D;
    if(D == 1 || D == 2 || D == 3) { cout << "Null" << endl; continue; }
    if(D >= 4) a = (D+sqrt(D*D-4*D)) / 2;
    else if(D == 0) a = 0;
    b = D - a;
    printf("%.9llf %.9llf\n", a, b);
  }
}

# [z023](https://judge.cp.ccns.io/problem/z023)：
明顯的，如果採用枚舉的方式一定會吃個 **TLE** (寫之前最好估計一下複雜度！)
改用**二分搜**加速，每次抽籤就找他的 lower bound:

int* l = lower_bound(LAN, LAN+N, lot);

以下完整程式碼：

#include<bits/stdc++.h>
using namespace std;

int const maxn = 1e6 + 10;

int N, LAN[maxn], T;

int main() {
  scanf("%d", &N);
  for(int i = 0; i < N; i++) scanf("%d", &LAN[i]);
  sort(LAN, LAN+N);

  scanf("%d", &T);
  while(T--) {
    int lot;
    scanf("%d", &lot);

    int* l = lower_bound(LAN, LAN+N, lot);

    if(*l == lot) printf("%d\n", lot);
    else if(l == LAN+N) printf("%d no\n", *(l-1));
    else if(l == LAN) printf("no %d\n", *l);
    else printf("%d %d\n", *(l-1), *l);
  }

  return 0;
}

# [z024](https://judge.cp.ccns.io/problem/z024)：
其實就是要找 $x$ 滿足 $f(x) = {{\sin(e^{-x})\cdot \sinh(x)}\over k} = 0.499$ 的地方
在題目中有提示 $k$ 越大，可以載重就越大，換句話說，$f$ 肯定是個遞增函數
因此用二分搜，`low = 0, up = 50`，開始搜，精度的問題請看 Code

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, i;
  int t;
  double low, up, mid, k;
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> k;
    low = 0, up = 50;
    while (up - low > 1e-12) {
      mid = (up + low) / 2;
      if (sin(exp(-mid)) * sinh(mid) / k > 0.499)
        up = mid;
      else
        low = mid;
    }
    cout << fixed << setprecision(9) << mid - 0.00000000049999999 << endl;
  }

  return 0;
}

# [z025](https://judge.cp.ccns.io/problem/z025)：

由於詢問的次數很高，所以期待每次的詢問複雜度不能太高，需要設計方便處理詢問的流程。
名詞說明：
- group: 每一個點所屬的組別編號，並且最終在當編號等於自身號碼時代表找到根。
- Find: group，並且做扁平加速。

可以參照[第四週教材 Union-Find Forest](https://hackmd.io/s/SJ7nxwRL4#Union-Find-Forest-%E4%BD%B5%E6%9F%A5%E6%A3%AE%E6%9E%97)

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;

int n, m, q;
int group[maxn];

int Find(int x) {
  if(group[x] == x) return x;
  return group[x] = Find(group[x]);
}

int main() {
  cin >> n >> m >> q;
  for(int i = 1; i <= n; i++) group[i] = i;

  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    group[Find(a)] = Find(b);
  }
  for(int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    cout << (Find(x) == Find(y)) << endl;
  }
  return 0;
}