1. 接水问题

来源：NOIP2010普及组 https://ac.nowcoder.com/acm/contest/238/C

算法：模拟

复杂度：

解题思路：

从前往后依次考虑队列中的每个同学，每个同学会去当前结束时间最早的水龙头处接水。

由于本题数据范围较小，因此可以直接循环一遍所有水龙头，求出当前结束时间最早的水龙头编号。那么我们就将当前同学安排在这个水龙头的位置上，然后将该水龙头的结束时间加上当前同学的接水时间。

最后，所有水龙头结束时间的最大值就是答案。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 10010,
    M = 110;

int n, m;
int w[N];
int q[M];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &w[i]);

    for (int i = 0; i < n; i++)
    {
        int t = 0;
        for (int j = 0; j < m; j++)
            if (q[j] < q[t])
                t = j;

        q[t] += w[i];
    }

    int res = 0;
    for (int i = 0; i < m; i++) res = max(res, q[i]);

    cout << res << endl;

    return 0;
}

 

2. 寻宝

来源：NOIP2012普及组 https://ac.nowcoder.com/acm/contest/240/C

算法知识点: 枚举，模拟

复杂度：

解题思路：

模拟从第 层走到第 层的整个过程，每次找出从当前房间开始第 个有梯子的房间即可。

最终每层遇到的 之和就是答案，不要忘记将答案对 取模。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 10010,
    M = 110,
    mod = 20123;

int n, m, k;
bool st[N][M];
int x[N][M];

int main()
{
    scanf("%d%d", &n, &m);

    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d%d", &st[i][j], &x[i][j]);

    scanf("%d", &k);
    for (int i = 0; i < n; i++)
    {
        int s = 0;
        for (int j = 0; j < m; j++) s += st[i][j];
        int t = x[i][k];
        res = (res + t) % mod;
        t %= s;
        if (!t) t = s;

        for (int j = k;; j = (j + 1) % m)
        {
            if (st[i][j])
            {
                if (--t == 0)
                {
                    k = j;
                    break;
                }
            }
        }
    }

    printf("%d\n", res);
    return 0;
}

 

3. 买铅笔

来源：NOIP2016普及组 https://ac.nowcoder.com/acm/contest/244/D

算法知识点: 模拟，枚举

复杂度：

解题思路：

由于老师只能买一种包装的铅笔，因此直接枚举买哪种包装，然后求出最少需要买多少包，才能使总数量不少于 即可。其中 是老师需要买的铅笔总数。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    int res = 1e9;
    for (int i = 0; i < 3; i++)
    {
        int s, p;
        scanf("%d%d", &s, &p);
        res = min(res, (n + s - 1) / s *p);
    }

    printf("%d\n", res);

    return 0;
}

 

4. 标题统计

来源：NOIP2018普及组 https://ac.nowcoder.com/acm/contest/293/A

算法知识点: 字符串处理

复杂度：

解题思路：

当用cin读入char类型时，会自动忽略空白字符，包括空格、制表符、回车等。

因此可以直接利用这个特性，统计总共读入多少个非空白字符即可。

C++ 代码：

#include <iostream>
using namespace std;

int main()
{
    char c;
    int s = 0;

    while (cin >> c) s++;

    cout << s << endl;
    return 0;
}

 
另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ