2020.8.1 猿辅导笔试算法题

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int maxn = 200200;
int n;
int x[maxn], y[maxn];
int h[maxn << 1], hcnt;
int f[maxn << 1];

int id(int x) {
  return lower_bound(h, h + hcnt, x) - h + 1;
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%d", &n)) {
    hcnt = 0;
    memset(f, 0, sizeof f);
    for (int i = 1; i <= n; i++) {
      scanf("%d %d", &x[i], &y[i]);
      h[hcnt++] = x[i];
      h[hcnt++] = y[i];
    }
    sort(h, h + hcnt);
    hcnt = unique(h, h + hcnt) - h;
    for (int i = 1; i <= n; i++) {
      f[id(x[i])]++;
      f[id(y[i])]--;
    }
    int ret = 0;
    for (int i = 1; i <= hcnt; i++) {
      f[i] += f[i - 1];
      ret = max(ret, f[i]);
    }
    printf("%d\n", ret);
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using pii = pair<LL, LL>;

const LL mod = 1E9 + 3;
const int maxn = 100100;
int n;
vector<int> G[maxn];
int root;
LL w[maxn];
double g[maxn];
LL f[maxn];

void dfs(int u, int p)  {
  f[u] = w[u];
  g[u] = double(w[u]);
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (v == p) continue;
    dfs(v, u);
    if (g[u] < g[u] + g[v]) {
      f[u] = (f[u] + f[v]) % mod;
      g[u] = g[u] + g[v];
    }
  }
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%d", &n)) {
    for (int i = 1; i <= n; i++) {
      G[i].clear();
    }
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    int u;
    for (int i = 1; i <= n; i++) {
      scanf("%lld %d", &w[i], &u);
      if (u == 0) {
        root = i;
        continue;
      }
      u--;
      G[i].emplace_back(u);
      G[u].emplace_back(i);
    }
    dfs(root, -1);
    LL ret = f[1];
    double tmp = g[1];
    for (int i = 2; i <= n; i++) {
      if (tmp < g[i]) {
        tmp = g[i];
        ret = f[i];
      }
    }
    printf("%lld\n", ret);
  }
  return 0;
}