京东笔试编程题 3.19

第一题

思路：直接模拟

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int i = 1, a, b, c, d, att = 0;
    cin >> a >> b >> c >> d;
    while(i ++) {
        int num = a / b;
        att += a % b;
        if(att >= b) {
            att -= b;
            d --;
        }
        d -= num;
        if(d <= 0) break;
        a -= d * c;
        if(a <= 0 && d > 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << i - 1 << endl;
    return 0;
}

第二题

思路：
每次加入具有最大权值边的节点到集合中；同时维护一个最大承重值，最大承重值为求其加入所有节点边的最小值
当时觉得时间复杂度还挺高的，没想到所有用例都过了

#include<iostream>
#include<vector>
#include<algorithm>
int t[1010][1010];
int visited[1010];
using namespace std;
int main() {
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n, m;
    int maxVal = 10010;
    cin >> n >> m;
    vector lt;
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        t[a][b] = c;
        t[b][a] = c;
    }
    for(int i = 1; i <= n; i++) {
        if(lt.size() == 0) {
            lt.push_back(1);
            visited[1] = 1;
        } else {
          int idx = 1, val = 0; 
          for(auto& num : lt) {   
              for(int j = 1; j <= n; j++) {
                  if(visited[j] == 0 && t[num][j] > val) {
                      val = t[num][j];
                         idx = j;
                  }
              } 
          }  
          lt.push_back(idx);
          maxVal = min(maxVal, val);
          visited[idx] = 1;
        }
    }
    cout << maxVal << endl;
    return 0;
}