2021-02-09 19:31 已编辑天津大学 Java

关注

牛客网OJ题解--20210202

牛牛的战役

https://ac.nowcoder.com/acm/problem/21613

本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC21613-牛牛的战役

题目链接

https://ac.nowcoder.com/acm/problem/21613

题目描述

牛牛逐渐成长，战斗力也渐渐增加，并可以指挥若干个oier协同作战

给你一个数组a表示我方每个人的战斗力

再给你一个数组b

再给你一个数组c

c[i]表示敌方b[i]战斗力的人有c[i]个

每个oier每次可以选择一名敌方人员进行战斗，如果战斗力大于等于敌方人员，就可以战胜，经验值+1

最开始的时候每个人的经验值都是0

现在牛牛想要打败所有敌方人员，也就是说每个敌方人员都要被一个oier所打败

但是牛牛想要最小化最大的经验值

如果不能打败所有的敌方人员，输出-1

否则输出最小化最大的经验值。

第一行输入一个整数n表示我方人员的数量(1 ≤ n ≤ 50)

第二行输入 n个整数ai表示我方每个人员的战斗力(1 ≤ ai ≤ 10000)

第三行输入一个整数m表示b数组的长度(1 ≤ m ≤ 50)

第四行输入m个整数bi (1 ≤ bi ≤ 10000)

第五行输入m个整数ci (1 ≤ ci ≤ 1014)

测试样例

样例1

输入

输出

样例2

输入

输出

样例3

输入

输出

-1

样例4

输入

1
1
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000

输出

2000000000000000

解题思路

参考的小毅儿解题思路，这里只是自己总结一下，我们根据样例1不难看出实际上就是尽可能每次都让所有能够比敌人战斗力大的伙伴能够平均收获经验值，如果不能平均收获经验值那么就是在整除的平均值基础上+1，这里主要是要能够找到比敌人战斗力大的我方战斗力最小的伙伴，这样才能够知道这次平均分配经验值要分配给几个人，一开始使用的暴力发现超时，后来发现原来可以用lower_bound返还不小于目标数值的索引值。问题迎刃而解。注意数值范围过大了要使用long long 。

解题代码

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

int a[55] = {};

struct enemy
//定义敌人结构体数组
{
    //敌人的战斗力
    int power;
    //power战斗力的人数
    long long num;
} b[55];

bool cmp(enemy x, enemy y)
{
    //重置比较规则为将敌人按照战斗力从小到大排序
    return x.power < y.power;
}

int main()
{
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    //将我方按战斗力从小到大排序
    sort(a + 1, a + 1 + n);
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i].power;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i].num;
    }
    //排序
    sort(b + 1, b + 1 + m, cmp);
    //敌方人数，我方中比敌方战斗力大的人，平均值
    long long sum = 0, s = 0, exper = -1;
    if (a[n] < b[m].power)
    //我方最强都打不过敌方直接退出
        cout << "-1" << endl;
    else
    {
        for (int i = m; i > 0; i--)
        {
            //每次都加上之前的敌人数量重新算平均经验值
            sum += b[i].num;
            //lower_bound返还不小于敌方战斗力的我方伙伴
            s = n + 1 - (lower_bound(a + 1, a + 1 + n, b[i].power) - a);
            //如果刚好平均分配
            if (sum % s == 0)
            {
                //记录平均数大的
                exper = max(exper, sum / s);
            }
            else
            {
                //如果不能平均分配，那么要+1
                exper = max(exper, sum / s + 1);
            }
        }
        cout << exper << endl;
    }
    system("pause");
    return 0;
}

NC50918-递归实现组合型枚举

题目链接

https://ac.nowcoder.com/acm/problem/50918

题目描述

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。 $n>0,0<=m<=n,n+(n-m)<=25$
还要注意要求按字典较小的顺序排列所有组合。

测试样例

输入

5 3

输出

解题思路

dfs深度搜索即可，主要是要注意当x>n时要停止。其实就是按照节点展开，第一行展开的是1->2,1->3,1->4,1->5的所有情况，然后接下来分别将2,3,4,5看成出发起点再次开始搜索，当这一组数值为m时就说明找到了一个组合输出。这样就自动保证了一定是按照字典从小到大的顺序输出组合了。同时要注意这个节点可选可不选，所以递归时有两种情况：

解题代码

#include <bits/stdc++.h>
using namespace std;
int n, m, answer[30];

void dfs(int start, int num)
{
    if (num == m + 1)
    //到达了叶子节点就是一组解输出
    {
        for (int i = 1; i <= m; i++)
            cout << answer[i] << " ";
        cout << endl;
        return;
    }
    if (start > n)
    //数值超出1~n范围了，退出
        return;
    //这个值
    answer[num] = start;
    //以这个节点的下一位为起点开始搜索
    dfs(start + 1, num + 1);
    //没有选这个节点，继续搜索
    dfs(start + 1, num);
}
int main()
{
    cin >> n >> m;
    //根节点就是从1开始
    dfs(1, 1);
    system("pause");
    return 0;
}