专栏首页落影的专栏程序员进阶之算法练习(四十)Codeforces

程序员进阶之算法练习(四十)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,时间和能力原因只完成了四道题,有兴趣的朋友可以接着去做。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员进阶之算法练习(十一)有感而发

    前言 经过这几年的观察,我发现,国内本科高校的ACM集训队,往往汇聚着该校相对靠谱的那一批人。 拿本校举例,队内的众学长学姐毕业之后,有去国内top2的高校...

    落影
  • Audio Unit播放aac/m4a/mp3等文件

    前言 相关文章: 使用VideoToolbox硬编码H.264 使用VideoToolbox硬解码H.264 使用AudioToolbox编码AAC 使...

    落影
  • 程序员进阶之算法练习(二十四)

    前言 已经有三个月未更新算法文章,大厂工作环境是步步紧逼的,使得所有的人越来越忙碌。余下的学习时间,要用于技术预研、知识面开阔、底层原理理解等等,慢慢算法只能占...

    落影
  • 时间就是生命:用树莓派和Wolfram神经网络创建虚拟飞行副驾

    "There's some good magic going on in that neural networks algorithm..."

    WolframChina
  • Xgboost初见面

    在 Kaggle 的很多比赛中,我们可以看到很多 winner 喜欢用 XGBoost,而且获得非常好的表现,今天就来看看 XGBoost到底是什么以及如何应用...

    IT派
  • 院士谭铁牛:智能化时代生物识别的机遇与挑战(附报告全文)

    大数据文摘
  • DeepMind为明年的AAAI,准备了一份各种DQN的混血

    夏乙 编译整理 量子位 出品 | 公众号 QbitAI ?DeepMind公开了一篇最近投递到AAAI 2018的新论文,这篇论文的主角,依然是这家公司四年前就...

    量子位
  • 浅谈JVM内存模型

    http://tutorials.jenkov.com/java-concurrency/java-memory-model.html

    CoffeeLand
  • 实战:简书爬取之多线程爬取(二)速度提升何止10倍

    其次就是这样的代码往往会有很严重的竞争问题,需要很多的资源锁来保证线程安全,这样就拉低了程序执行的速度。

    渔父歌
  • Python+Selenium 定位页面

    1.跳转到Frame/Iframe ,再定位元素 理解:frame的实质,frame中实际上是嵌入了另一个页面,而webdriver每次只能在一个页面识别,因此...

    py3study

扫码关注云+社区

领取腾讯云代金券