程序员进阶之算法练习（四十）Codeforces

正文

题目1

题目链接 题目大意： 在一维坐标轴上有三个点，坐标是a、b、c； 现在需要移动这三个点的位置，使得三个点之间两两间隔大于d； 每次只能移动一个点，每秒只能移动距离1； 问最少需要多少秒，才能满足要求。

输入： 一行，四个数字 ?, ?, ?, ? (1≤?,?,?,?≤10^9)

输出： 最少的秒数。

Examples input 5 2 6 3 output 2

题目解析： a、b、c之间没有关系，可以先排序，使得a<b<c。 使得x=b-a, y=c-b，那么有： x>=d的时候，ans=max(0, d-y); y>=d的时候，ans=max(0, d-x); 都不满足的时候，ans=(d-x)+(d-y);

    int a[3], d, ans = 0;
    cin >> a[0] >> a[1] >> a[2] >> d;
    sort(a, a + 3);
    int x = a[1] - a[0], y = a[2] - a[1];
    if (x >= d) {
        ans = max(0, d - y);
    }
    else if (y >= d) {
        ans = max(0, d - x);
    }
    else {
        ans = (d - x) + (d - y);
    }
    cout << ans << endl;

题目2

题目链接 题目大意： 小明用键盘的打字，但是键盘出现故障，每次敲击可能会出现多次结果，比如说按一次h，可能会出现"h"、"hh"、"hhh"等； 现在给出小明打字的原始字符串和目标字符串，问目标字符串是否可能出现？ 比如说原始串是"hello"，那么目标串可以为"hello", "hhhhello", "hheeeellllooo"，但不能为"hell", "helo", "hhllllooo"。

输入： 第一行是整数t，表示t个样例； 每个样例有2行输入，第1行是原始字符串，第2行是目标字符串；

输出： 对于每个样例，如果可能出现则输出YES，不可能则输出NO。

Examples input 5 aa bb codeforces codeforce polycarp poolycarpp aaaa aaaab abcdefghijklmnopqrstuvwxyz zabcdefghijklmnopqrstuvwxyz output NO NO YES NO NO

题目解析： 我们用sourceStr和targetStr来表示原始字符串和目标字符串，根据题目的要求： 1、sourceStr是targetStr的子序列； 2、sourceStr中间某些单词会重复，并且targetStr与sourceStr不同的部分，均由这个重复的单词组成。

基于此，可以从左到右遍历sourceStr和targetStr，用x和y分别来表示sourceStr和targetStr的当前遍历进度； 初始时，x=0, y=0； 如果sourceStr[x]==targetStr[y]，表示同时出现一个字符，那么直接++x和++y； 如果sourceStr[x]!=targetStr[y]，如果是普通字符串匹配，此时会fail，但是这里有题目要求2的特点，targetStr[y]可能是sourceStr[x-1]的重复；所以如果sourceStr[x-1]==targetStr[y]，仍然可以++y，此时x不动；

最后注意把y补齐，判断是否能否x==strlen(sourceStr)，y==strlen(targetStr)，表示是否填充完毕。

    int n;
    cin >> n;
    while (n--) {
        string a, b;
        cin >> a >> b;
        int x = 0, y = 0;
        while (x < a.length() && y < b.length()) {
            if (a[x] == b[y]) {
                ++x;
                ++y;
            }
            else {
                if (x > 0 && b[y] == a[x - 1]) {
                    ++y;
                }
                else {
                    break;
                }
            }
        }
        while (y < b.length()) {
            if (a.back() == b[y]) {
                ++y;
            }
            else {
                break;
            }
        }
        if (x == a.length() && y == b.length()) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }

题目3

题目链接 题目大意： n个人参加测试，测试需要老师和学生一对一进行，同一时刻只能有一个学生在测试，每个人测试的耗时可能不同； 现在按照1~n的顺序进行测试，已知测试的总时间为m，每个人的测试时间为t[i]； 老师想要知道，对于第i个人，最少需要直接放弃前面多少个人，才能有足够的时间让其能在规定时间m内完成测试；（每个人是相对独立的，对于第i个人和第i+1个人，放弃的人可能各不相同）

输入： 输入共两行 第一行两个整数n and m，分别表示n个人和测试总时间m (1≤n≤100, 1≤m≤100) 第二行是n个整数t[i]，分别表示n个人的测试时间。(1≤?[?]≤100)

输出： 对于每个人，输出通过测试，需要放弃的最少人数；

Examples input 7 15 1 2 3 4 5 6 7 output 0 0 0 0 0 2 3

样例解释： 对于前5个人，都不需要放弃任何人即可完成测试； 对于第6个人，可以放弃第3、4个人，剩下的人可以完成测试； 对于第7个人，可以放弃第3、4、5个人，剩下的人可以完成测试；

题目解析： 题目的数据范围比较小，可以使用较为粗暴的方式： 记录前i个人的耗时之和sum，如果sum>m，则对前i个人排序，然后从大的开始淘汰，直到sum<=m即可。

    int n, m;
    cin >> n >> m;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
        if (sum <= m) {
            ans[i] = 0;
        }
        else {
            sort(a, a + i);
            int tmp = sum;
            while (tmp > m) {
                ++ans[i];
                tmp -= a[i - ans[i]];
            }
        }
    }
    
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << " ";
    }
    cout << endl;

题目4

题目链接 题目大意： n个人参加测试，测试需要老师和学生一对一进行，同一时刻只能有一个学生在测试，每个人测试的耗时可能不同； 现在按照1~n的顺序进行测试，已知测试的总时间为m，每个人的测试时间为t[i]； 老师想要知道，对于第i个人，最少需要直接放弃前面多少个人，才能有足够的时间让其能在规定时间m内完成测试；（每个人是相对独立的，对于第i个人和第i+1个人，放弃的人可能各不相同）

输入： 第一行两个整数n and m ，分别表示n个人和测试总时间m (1≤n≤2⋅1e5, 1≤m≤2⋅1e7) 第二行是n个整数t[i]，分别表示n个人的测试时间。(1≤?[?]≤100)

输出： 对于每个人，输出通过测试，需要放弃的最少人数；

Examples input 7 15 1 2 3 4 5 6 7 output 0 0 0 0 0 2 3

样例解释： 对于前5个人，都不需要放弃人即可完成测试； 对于第6个人，可以放弃第3、4个人，剩下的人可以完成测试； 对于第7个人，可以放弃第3、4、5个人，剩下的人可以完成测试；

题目解析： 相对上一题，这里的数据量更加大。如果再每次排序，复杂度会到达O(N^2logN)的级别。 这里可以用优先队列来进行优化： 维持两个队列，一个是大顶堆top_queue，表示所有已经选中参加考试的人的耗时； 一个是小顶堆tmp_queue，表示所有已经没有被选中参加考试的人的耗时； 从左到右遍历每个人，对于第i个人，如果top_queue中所有人的耗时加上a[i]，仍小于等于m，则答案为tmp_queue的size； 如果top_queue中所有人的耗时加上a[i]大于m，则表示top_queue中的人某些人需要被放弃； 我们从耗时最长的人开始放弃，直到top_queue的总耗时+a[i]<=m，放弃的人都放入tmp_queue，此时答案为tmp_queue的size；

在得到第i个人的耗时之后，将a[i]放入tmp_queue，然后不断从tmp_queue取出最小值x，如果top_queue的总耗时+x<=m，则可以把x放入top_queue。

对于第i个人，top_queue 相当于前i-1个人中，总耗时不大于m的集合，top_queue.top为耗时最长的人； tmp_queue 表示没被选中人的集合，tmp_queue.top为耗时最短的人；

这个解决理论上是OK的，但是在case13会遇到RunTime Error，比较奇怪；最后查出来是数组越界，但是RE报错在一些完全无关的地方。 fix这个bug之后，顺利通过。

其他思路： 观察题目的数据范围，发现每个人的分数范围是[1, 100]，那么可以用一个人数组来做聚合，避免重复的排序。 a[i] 表示分数为i的人数； 对于第i个人，假设其耗时是k，总耗时不能超过m，那么其他人的耗时是left_time=m-k； 从1~100去遍历分数，对于分数为i的人数有a[i]个；

int t = min(a[j], left_time / j);
cnt += t;
left_time -= t * j;

我们选中了t个分数为i的人。 从小到大遍历一次，相当于我们从分数小的开始选，一直到不能选为止，得到总耗时不超过(m-k)的有cnt个人。 那么答案就是剩下的人。

总结

题目1是简单题，注意a/b/c的大小是随机，但题目样例也给出这种case； 题目2是字符串匹配，细节是x和y匹配到边界的处理，非常容易出错； 题目3是暴力枚举，要发现题目范围小； 题目4是贪心，题目3的基础加大数据范围，可以选择用数据结构来优化处理速度，也可以从题目较小的数据范围入手，更好的针对题目进行优化；

以上题目均来自http://codeforces.com/contest/1185，时间和能力原因只完成了四道题，有兴趣的朋友可以接着去做。