美团8.13后端笔试题cpp复盘

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
  int n, t;
    cin >> n >> t;  // n为订单数，t为每单派送时间
  int num;        
  vector<int> nums(n);  // n个订单的超时时间
  for(int i = 0; i < n; ++i) {
      cin >> num;
    nums[i] = num;
  }
  sort(nums.begin(), nums.end());
  int count = 0;     // 最少使用几次魔法
  int time = 0;      // 配送花费总时间
  for(int i = 0; i < n; ++i) {
    if(t + time <= nums[i]) { // 时间小于等于超时时间则不需要使用魔法
      time += t;
    }
    ++count;
  }
  cout << count << endl;
  return 0;
}

#include<iostream>
#include<vector>
#include<algrithm>

using namespace std;

int main() {
    int n, m, k; // n*m房间,k长度指令字符串，均为大写
  cin >> n >> m >> k;
  string str;
  cin >> str;
  vector<vector<bool>> map(n, vector<bool>(m, false));
  int x = 0, y = 0;
  map[x][y] = true;
  int clean = 1; // 记录已清理的数量
  int i;
  for(i = 0; i < k; ++i) {
    if(str[i] == 'W') {    // 上
      if(x > 0) {
        --x;
      }
     }
    if(str[i] == 'S') {    // 下
      if(x + 1 < n) {
        ++x;
      }
    }
    if(str[i] == 'A') {    // 左
        if(y > 0) {
        --y;
      }
    }
    if(str[i] == 'D') {    // 右
      if(y + 1 < m) {
        ++y;
      }
    }
    if(map[x][y] == false) {
        ++clean;
      map[x][y] = true;
    }
    if(clean == n * m) break;
  }
  if(clean == n * m) {
      cout << "Yes" << endl;
    cout << i + 1;
  } else {
      cout << "No" << endl;
    cout << n * m - clean;
  }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>

using namespace std;

int main() {
  int n;  // n张牌
  cin >> n;
  vector<int> nums(n);
  int num;
  for(int i = 0; i < n; ++i) {
    cin >> num;
    nums[i] = num;
  }
  deque<int> myDeque;
  for(int i = n - 1; i >= 0; --i) {
    myDeque.push_front(nums[i]);
    int people = 2;
    while(people--) {
      myDeque.push_front(myDeque.back());
      myDeque.pop_back();
    }
  }
  for(const auto& it : myDeque) {
    cout << it << " ";
  }
  return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

vector<int> path;
void backtracing(vector<int>& nums, int startIndex, int& ans) {
  if(path.size() > 3) return;
  if(path.size() == 3) {
    if((path[0] - path[1]) - (2 * path[1] - path[2]) == 0) {
      ++ans;
    }
    return;
  }
  for(int i = startIndex; i < nums.size(); ++i) {
    path.push_back(nums[i]);
    backtracing(nums, i + 1, ans);
    path.pop_back();  // 回溯
  }  
}

int main() {
  int n;  // 序列长度
  cin >> n;
  vector<int> nums(n);
  int num;
  for(int i = 0; i < n; ++i) {
    cin >> num;
    nums[i] = num;
  }
  int ans = 0;
  backtracing(nums, 0, ans);
  cout << ans << endl;
  return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int traversal(vector<int>& nums, int index, int length) {
  if(index >= length) return 0;
  int l = traversal(nums, 2 * index, length) + nums[index];  // 左子树
  int r = traversal(nums, 2 * index + 1, length) + nums[index]; // 右子树
  return max(l, r);
}

int main() {
  int n;  // 序列长度
  cin >> n;
  vector<int> nums(n + 1);
  nums[0] = 0;
  int num;
  for(int i = 1; i < n + 1; ++i) {
    cin >> num;
    nums[i] = num;
  }
  int res = traversal(nums, 1, nums.size());
  cout << res << endl;
  return 0;
}