10.15 滴滴笔试

1、能够同时操作的最大个数；思路：排序后暴力 100%；本来想优化的，结果直接过了haha;

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

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> nums(n);
  for(int i=0; i< n; i++){
    cin >> nums[i];
  }
  sort(nums.begin(), nums.end());
  int ret = 0;
  for(int i=0; i< n-ret; i++){
    int j = i;
    while(j< n&& nums[j]-nums[i]<= k) j += 1;
    ret = max(ret, j-i);
  }
  cout << ret;
  return 0;
}

2、安排不同的路线总数；思路：先按照区间开始和末尾排序，然后计算从当前开始到末尾有重合的个数，然后选取就好了；100%

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<pair<int, int>> plans(n);
  unordered_map<int, int> has_inter;
  for(int i=0; i< n; i++){
    cin >> plans[i].first;
  }
  for(int i=0; i< n; i++){
    cin >> plans[i].second;
  }
  sort(plans.begin(), plans.end());
  for(int i=0; i< n; i++){
    int left =i+1, right = n-1;
    while(left<= right){
      int mid = (left+right)/2;
      if(plans[mid].first<= plans[i].second)
        left = mid+1;
      else
        right = mid-1;
    }
    has_inter[i] = left-i-1;
  }
  
  vector<int> post(n, 0);
  for(int i=n-1; i>= 0; i--){
    post[i] = (n-i-1) - has_inter[i];
    if(i != n-1)
      post[i] += post[i+1];
  }
  
  long ret = 0;
  for(int i=0; i< n; i++){
    int j=i+1;
    while(j< n&& plans[j].first<= plans[i].second)
      j += 1;
    if(j< n)
      ret += post[j];
  }
  cout << ret;
  return 0;
}

美团、百度、小米等大厂都AK了，到现在都没有面试，大厂的笔试做着玩玩就好了；