2022年3月19日京东机试编程题

第一题

攻城战

时间限制： 1000MS内存限制： 65536KB

题目描述：

小七正在玩一款名为“攻城战”的策略游戏。现在，小七正在率领自己的军队攻打一座城池。通过一段时间的游玩，小七的军队目前有a辆坦克。而“攻防战”是一个回合制游戏，一个回合如下：

1.小七的军队中的每辆坦克攻击所选择的一座碉堡，这座碉堡损失一点生命值。当一座碉堡失去所有生命值时，它就被摧毁了。小七可以为每辆坦克独立选择碉堡。

2.小七的对手进攻。炸毁k*c辆坦克，其中：k是剩余的碉堡的数量，每个碉堡可以炸毁c辆坦克。

通过侦察兵，小七探明了敌情：战场上有d座敌方碉堡，每一座碉堡都有b点生命值。摧毁所有的碉堡后，小七就攻下了这座城池（即使小七没有坦克了，也算攻下了这座城池）。反之如果小七没有坦克了，敌方还有碉堡，小七就失败了。现在小七想提前知道自己能否获胜，你能帮帮小七吗？

输入描述：

一行四个空格隔开的整数a,b,c,d，其中1<=a<=1000000, 1<=b,c,d<=10000

输出描述

输出一个数，如果小七可以获胜，输出所需的最小回合数。否则输出-1。

​

• 样例输入

  10 6 8 2

• 样例输出

  2

我的代码：

```cpp
#include <iostream>
using namespace std;

int main()
{

    int a, b, c, d; // a代表目前有a辆坦克，b代表每一座碉堡都有b点生命值，c代表对手进攻炸毁k*c辆坦克(k是剩余的碉堡数量)，d代表战场上有d座敌方碉堡
    /*
    input：10 6 8 2  一共碉堡有2*6=12滴血 坦克有10辆
    output：2
    */
    cin >> a >> b >> c >> d;
    int circle = 0;
    int blood = b * d;
    int tank = a;
    while (tank > 0 && blood > 0)
    {
        circle++;
        blood -= tank;
        d = blood / b + 1;
        tank -= c * d;
    }
    if (blood > 0)
    {
        cout << -1;
    }
    else
    {
        cout << circle;
    }
    return 0;
}
```

第二题

建造规划

时间限制： 1000MS 内存限制： 65536KB

题目描述：

小明在玩一款建造类的游戏。他需要为一段未开荒的地段设计路段的规划，以便起重机通过。

游戏里每段路径都有能承重的级别，小明现在希望尽可能让能承重更大的起重机通过，这样他就可以比较快地完成建造了。

游戏规定小明只能选一种起重机机型，小明想知道这个起重机最高的承重级别应该是多少，使得在该承重条件下，起重机可以从任何一个点出发去向任何一个点而不会损坏道路（损坏道路指的是路段上行驶了超过承重能力的起重机）。

为了方便，我们将需要规划的建造点抽象成N个点，有M条边将他们相连。

输入描述

第一行是两个空格隔开的正整数n,m。n代表点数，我们将点从1到n编号，m指边的数量。接下来m行，每行3个空格隔开的正整数u, v, p，代表节点u和节点v之间有一条承重能力为p的路径。

输出描述

一行，一个正整数，表示起重机的最重承重级别。

• 样例输入

3 3
1 2 3
1 3 4
2 3 5

• 样例输出

4

提示：

样例解释：重量为5时，从点1到点3无法完成（超出了最大承重），而重量为4时可以任意两点间达到。因此最重可以是4。

我的代码：

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

using namespace std;

struct Paths
{
    int from;
    int go;
    int weight;
};

bool cmp(Paths p1, Paths p2)
{
    return p1.weight > p2.weight;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<Paths> all(m);
    map<int, int> maps;
    for (int i = 1; i <= n; i++)
    {
        maps[i] = 0;
    }
    for (int i = 0; i < m; i++)
    {
        cin >> all[i].from >> all[i].go >> all[i].weight;
        if (maps[all[i].from] < all[i].weight)
        {
            maps[all[i].from] = all[i].weight;
        }
        if (maps[all[i].go] < all[i].weight)
        {
            maps[all[i].go] = all[i].weight;
        }
    }

    int min = INT_MAX;

    for (auto &i : maps)
    {
        if (i.second < min)
            min = i.second;
    }

    cout << min << endl;

    return 0;
}