牛客网OJ题解--20210309

良神吃点心

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

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

NC14705-良神吃点心

题目链接

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

题目描述

良神爱吃甜点，如果他吃不到甜点的话就会很暴躁！现在桌子上摆着一排n个点心，每个点心具有一个甜度ai，良神一次能吃连续的一些点心，但是他一次不能吃总甜度和超过m（可以等于m），否则他就长不高啦！良神想要知道他最少吃几次才能把这些点心都吃完。

第1行输入两个整数n，m，代表点心数量和一次可以吃的总甜度上限。

第2行输入n个整数，第i个整数代表第i个点心的甜度ai。

数据保证：0<n≤100，0<ai≤100，m≥ai的最大值。

输出一行，一个整数，代表良神吃的最少次数。

测试样例

样例1

输入

5 6
4 2 4 5 1

输出

说明

良神可以按照[4 2][4][5 1]的方式吃点心，最少需要3次吃完。

样例2

输入

5 6
6 6 6 6 6

输出

说明

良神可以按照[6][6][6][6][6]的方式吃点心，最少需要5次吃完。

解题思路

简单，就是从左往右吃，吃到能容忍的最大程度就重新吃几颗，主要是注意下每一次重新吃容忍度刷新为0，并且最后一次可能吃不到最大容忍度就结束啦，那也算吃一次。

解题代码

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

int a[105];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    //甜度
    int tmp = 0;
    //次数
    int ans = 0;
    int j = 1;
    while (j <= n)
    {
        tmp += a[j];
        //甜度大于m了，说明不吃j时是本次可以吃的最大程度
        if (tmp > m)
        {
            //将第j个甜品吐出来不吃可以承受
            tmp -= a[j];
            //tmp归零为下一次吃初始化
            tmp = 0;
            //吃的次数+1
            ans++;
            //j就不加了，因为j还没吃呢
            continue;
        }
        j++;
    }
    //坑点，如果最后一次吃完还没到最大承受度
    //那么也算一次吃了
    if (tmp != 0)
        ans++;
    cout << ans << endl;
    system("pause");
    return 0;
}

NC14965-大吉大利，今晚吃鸡——枪械篇

题目链接

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

题目描述

在绝地求生（吃鸡）游戏里，不同的枪支有不同的威力，更是可以搭配不同的配件，以提升枪支的性能。

每一把枪都有其威力及其可装备配件种类。每一个配件有其所属种类，可以为枪支提供威力的百分比加成。每一把枪只能装备一个同类配件。给你n把枪支和m个配件，枪的威力为p，可装备的配件数量为k，为k个不同类型的配件，同种类配件只可以装备一个。配件种类用数字q表示，配件威力加成用一个小数b表示。请你挑选一把枪并为其搭配配件使其威力最大。假设一把枪的威力是p，装配的k个配件的威力加成是bi，那么枪最后的威力w=p*（1+b1+b2+…+bk）。

数据有多组，处理到文件结束。
第一行两个整数n和m，代表枪支数量和配件数量。
接下来n行，描述n把枪的属性：第一个整数为p，代表枪支的威力；第二个整数为k，代表该枪支可装备的配件数量；后面k个整数，代表可装备配件的种类。
接下来m行，描述m个配件的属性：第一个整数为q，代表配件的种类，第二个浮点数为b，代表配件可以为枪支提供的威力加成。

每组数据输出为一行，输出一个浮点数，代表合理装备配件后的枪支最大威力。精确到小数点后4位。

对于100%的数据，1 <= n,m,k,q <= 1000;0 <= p <= 1000;

测试样例

输入

3 6
120 3 1 2 3
100 4 1 2 3 4
110 3 2 3 4
1 0.12
2 0.23
2 0.26
4 0.57
3 0.35
5 0.41

输出

239.8000

说明

对于上面的样例，正确答案应该是，使用第三把枪，配上第三、四、五个配件。
枪的最终威力就是110*（1+0.26+0.57+0.35）=239.8

解题思路

这道题实际上就是一个暴力枚举，但是比较锻炼读题能力，思路就是输入数据时将每一个最大类型的***属性记录下来，然后注意求得每一把枪满配的战斗力，然后取最大战斗力。

解题代码

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

struct Gun
{
    //枪的初始战斗力
    double num;
    //枪支持的配件数
    int len;
    //枪支持的配件号
    int a[1005];
} gun[1005];
//配件加强数值数组
double plugin[1005];

//计算每把枪的最理想战斗力
double Count(int x)
{
    double sum = 1;
    for (int i = 1; i <= gun[x].len; i++)
    {
        //这里要注意，较难想
        sum += plugin[gun[x].a[i]];
    }
    return gun[x].num * sum;
}

int main()
{
    int n, m;
    cin >> n >> m;
    //存储枪的初始数据
    for (int i = 1; i <= n; i++)
    {
        cin >> gun[i].num;
        cin >> gun[i].len;
        for (int j = 1; j <= gun[i].len; j++)
        {
            cin >> gun[i].a[j];
        }
    }
    //记录每一个型号的枪件最强属性
    for (int i = 1; i <= m; i++)
    {
        int index;
        double tmp;
        cin >> index >> tmp;
        plugin[index] = max(plugin[index], tmp);
    }
    double ans = 0.0;
    for (int i = 1; i <= n; i++)
    {
        if (ans < Count(i))
            ans = Count(i);
    }
    cout << fixed << setprecision(4) << ans << endl;
    system("pause");
    return 0;
}