9.4 滴滴笔试编程题题解

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

int main() {
  using ll = long long;
  int n, k; cin >> n >> k;
  vector<int> v(n);
  for (int i = 0; i < n; i++) cin >> v[i];
  sort(v.begin(), v.end());
  vector<ll> preSum(n+1);
  for (int i = 1; i <= n; i++) {
    preSum[i] = preSum[i-1] + v[i-1];
  }
  auto ck = [&] (int m) -> bool {
    for (int i = 0; i < n-m+1; i++) {
      if (1.0*(preSum[i+m]-preSum[i])/m*k >= v[i+m-1]) {
        return true;
      }
    }
    return false;
  };
  int low = 1, high = n;
  int ans = 1;
  while (low <= high) {
    int m = (low+high)/2;
    if (!ck(m)) {
      high = m-1;
    } else {
      ans = m;
      low = m+1;
    }
  }
  cout << ans << endl;
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
  vector<vector<int>> cnt(70001, vector<int>(20));
  cnt[0][0] = 1;
  for (int i = 1; i < 70001; i++) {
    int s = 0, tmp = i;
    while (tmp) {
      s ^= tmp % 10;
      tmp /= 10;
    }
    for (int j = 0; j < 16; j++) {
      cnt[i][j] = cnt[i-1][j]+(j==s);
    }
  }
  int n; cin >> n;
  vector<int> l(n), r(n), t(n);
  for (int i = 0; i < n; i++) cin >> l[i];
  for (int i = 0; i < n; i++) cin >> r[i];
  for (int i = 0; i < n; i++) cin >> t[i];

  for (int i = 0; i < n; i++) {
    if (t[i] >= 16) {
      cout << 0 << " ";
      continue;
    }
    cout << cnt[r[i]][t[i]] - (l[i] ? cnt[l[i]-1][t[i]] : 0) << " ";
  }
  cout << endl;
  return 0;
}