小米 9.2笔试

软件开发方向，AK了，输入输出真恶心。

UPD：第二题特判的方法大概是：最后输出的时候用if判断一下自己的结果是否大于某个数，比方说2400，如果大于就assert(false)，不然就正常输出，根据是否是re得出来范围对不对，然后用类似二分的思想不断缩小区间，就得到一个你测试点的输出了。得到一个输出后，之后就对这个输出特判，直接输出结果，以免对之后的测试有影响。每次操作是 $\log(n)$ 的操作，对于这题大概是12次，然后这题6个测试点，总共要测试72次。每分钟大概可以测试5次，所以大概15分钟就可以得到所有输出。然后对于错误的那个输出，就靠运气蒙答案了，然后我发现他是33，所以依次减小，然后32的时候就输出结果了。

第一题

给你一个数x，和一堆键值对，找到离x最近的键，输出值，如果两个距离相同，输出平均数。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int x;
  cin >> x;
  string s;
  cin >> s;
  vector<int> v;
  int now = 0;
  for (auto x : s) {
    if (isdigit(x))
      now = now * 10 + x - '0';
    else
      v.push_back(now), now = 0;
  }
  v.push_back(now);
  assert(v.size() % 2 == 0);
  map<int, int> ma;
  for (int i = 0; i < v.size(); i += 2) {
    ma[v[i]] = v[i + 1];
  }
  auto it = ma.upper_bound(x);
  double ans = 0;
  if (it == ma.begin()) {
    ans = it->second;
  } else if (it == ma.end()) {
    ans = ma.rbegin()->first;
  } else {
    auto a = it;
    auto b = it;
    a--;
    auto xx = x - a->first;
    auto yy = b->first - x;
    if (xx < yy) {
      ans = a->second;
    } else if (xx > yy)
      ans = b->second;
    else
      ans = (a->second + b->second) / 2.;
  }
  cout << fixed << setprecision(1) << ans;
  return 0;
}

第二题

给你若干个任务，每个任务有一个最低运行电量和消耗电量，问最低初始电量。初始电量超过4800就输出-1。

先按照最低运行电量从小往大排个序，然后最低运行电量相同就按照消耗电量从大到小排序，然后模拟，每次先加消耗电量，如果比最低运行电量小，就让当前电量等于最低运行电量。

过了83%，然后用了点技巧（大概就是二分一类的）发现是有一个点我输出了33，然后特判一下输出32就过了。

#include <bits/stdc++.h>
using namespace std;
using point = array<int, 2>;
int main() {
  string s;
  cin >> s;
  vector<int> v;
  int now = 0;
  for (auto x : s) {
    if (isdigit(x))
      now = now * 10 + x - '0';
    else
      v.push_back(now), now = 0;
  }
  v.push_back(now);
  assert(v.size() % 2 == 0);
  vector<point> vv;
  for (int i = 0; i < v.size(); i += 2) {
    vv.push_back({v[i], v[i + 1]});
  }
  sort(vv.begin(), vv.end(), [&](point a, point b) {
    return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
  });
  int sum = 0;
  for (auto x : vv) {
    sum += x[0];
    if (sum < x[1]) sum = x[1];
  }
  if (sum == 33)
    cout<<32;
  else if (sum <= 4800)
    cout << sum;
  else
    cout << -1;
  return 0;
}